Celestia

1
// r128util.cpp
2
//
3
// Copyright (C) 2007-present, Celestia Development Team
4
// Original version by Chris Laurel <claurel@shatters.net>
5
//
6
// 128-bit fixed point (64.64) numbers for high-precision celestial
7
// coordinates. When you need millimeter accurate navigation across a scale
8
// of thousands of light years, double precision floating point numbers
9
// are inadequate.
10
//
11
// This program is free software; you can redistribute it and/or
12
// modify it under the terms of the GNU General Public License
13
// as published by the Free Software Foundation; either version 2
14
// of the License, or (at your option) any later version.
15

16
#include <array>
17
#include <cassert>
18
#include <cmath>
19
#include <cstddef>
20
#include <cstdint>
21

22
#define R128_IMPLEMENTATION
23
#include "r128util.h"
24

25
using namespace std::string_view_literals;
26

27
namespace
28
{
29

30
constexpr std::string_view alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"sv;
31
static_assert(alphabet.size() == 64, "Base64 decoder alphabet must be of length 64");
32

33
constexpr std::uint8_t AsciiRange = 128;
34

35
using DecoderArray = std::array<std::int8_t, AsciiRange>;
36

37
DecoderArray createBase64Decoder()
38
{
39
    DecoderArray decoder;
40
    decoder.fill(-1);
41
    for (std::size_t i = 0; i < alphabet.size(); ++i)
42
    {
43
        std::uint8_t idx = static_cast<std::uint8_t>(alphabet[i]);
44
        assert(idx < AsciiRange);
45
        decoder[idx] = static_cast<std::int8_t>(i);
46
    }
47

48
    return decoder;
49
}
50

51
} // end unnamed namespace
52

53
namespace celestia::util
54
{
55

56
std::string EncodeAsBase64(const R128 &b)
57
{
58
    // Old BigFix class used 8 16-bit words. The bulk of this function
59
    // is copied from that class, so first we'll convert from two
60
    // 64-bit words to 8 16-bit words so that the old code can work
61
    // as-is.
62
    std::array<std::uint16_t, 8> n =
63
    {
64
        static_cast<std::uint16_t>(b.lo),
65
        static_cast<std::uint16_t>(b.lo >> 16),
66
        static_cast<std::uint16_t>(b.lo >> 32),
67
        static_cast<std::uint16_t>(b.lo >> 48),
68

69
        static_cast<std::uint16_t>(b.hi),
70
        static_cast<std::uint16_t>(b.hi >> 16),
71
        static_cast<std::uint16_t>(b.hi >> 32),
72
        static_cast<std::uint16_t>(b.hi >> 48),
73
    };
74

75
    // Conversion using code from the original R128 class.
76
    std::string encoded;
77
    int bits, c, char_count, i;
78

79
    char_count = 0;
80
    bits = 0;
81

82
    // Find first significant (non null) byte
83
    i = 16;
84
    do {
85
        i--;
86
        c = n[i/2];
87
        if ((i & 1) != 0) c >>= 8;
88
        c &= 0xff;
89
    } while ((c == 0) && (i != 0));
90

91
    if (i == 0)
92
        return encoded;
93

94
    // Then we encode starting by the LSB (i+1 bytes to encode)
95
    for (auto j = 0; j <= i; j++)
96
    {
97
        c = n[j/2];
98
        if ( (j & 1) != 0 ) c >>= 8;
99
        c &= 0xff;
100
        bits += c;
101
        char_count++;
102
        if (char_count == 3)
103
        {
104
            encoded += alphabet[bits >> 18];
105
            encoded += alphabet[(bits >> 12) & 0x3f];
106
            encoded += alphabet[(bits >> 6) & 0x3f];
107
            encoded += alphabet[bits & 0x3f];
108
            bits = 0;
109
            char_count = 0;
110
        }
111
        else
112
        {
113
            bits <<= 8;
114
        }
115
    }
116

117
    if (char_count != 0)
118
    {
119
        bits <<= 16 - (8 * char_count);
120
        encoded += alphabet[bits >> 18];
121
        encoded += alphabet[(bits >> 12) & 0x3f];
122
        if (char_count != 1)
123
            encoded += alphabet[(bits >> 6) & 0x3f];
124
    }
125

126
    return encoded;
127

128
}
129

130
R128 DecodeFromBase64(std::string_view val)
131
{
132
    static DecoderArray decoder = createBase64Decoder();
133

134
    std::array<std::uint16_t, 8> n = {0};
135

136
    // Code from original BigFix class to convert base64 string into
137
    // array of 8 16-bit values.
138
    int char_count = 0;
139
    int bits = 0;
140

141
    int i = 0;
142

143
    for (unsigned char c : val)
144
    {
145
        if (c == '=')
146
            break;
147
        if (c >= AsciiRange)
148
            continue;
149
        std::int8_t decoded = decoder[c];
150
        if (decoded < 0)
151
            continue;
152
        bits += decoded;
153
        char_count++;
154
        if (char_count == 4)
155
        {
156
            n[i/2] >>= 8;
157
            n[i/2] += (bits >> 8) & 0xff00;
158
            i++;
159
            n[i/2] >>= 8;
160
            n[i/2] += bits & 0xff00;
161
            i++;
162
            n[i/2] >>= 8;
163
            n[i/2] += (bits << 8) & 0xff00;
164
            i++;
165
            bits = 0;
166
            char_count = 0;
167
        }
168
        else
169
        {
170
            bits <<= 6;
171
        }
172
    }
173

174
    switch (char_count)
175
    {
176
    case 2:
177
        n[i/2] >>= 8;
178
        n[i/2] += (bits >> 2) & 0xff00;
179
        i++;
180
        break;
181
    case 3:
182
        n[i/2] >>= 8;
183
        n[i/2] += (bits >> 8) & 0xff00;
184
        i++;
185
        n[i/2] >>= 8;
186
        n[i/2] += bits & 0xff00;
187
        i++;
188
        break;
189
    }
190

191
    if ((i & 1) != 0)
192
        n[i/2] >>= 8;
193

194
    // Now, convert the 8 16-bit values to a 2 64-bit values
195
    std::uint64_t lo = (static_cast<std::uint64_t>(n[0])
196
                        | (static_cast<std::uint64_t>(n[1]) << 16)
197
                        | (static_cast<std::uint64_t>(n[2]) << 32)
198
                        | (static_cast<std::uint64_t>(n[3]) << 48));
199
    std::uint64_t hi = (static_cast<std::uint64_t>(n[4])
200
                        | (static_cast<std::uint64_t>(n[5]) << 16)
201
                        | (static_cast<std::uint64_t>(n[6]) << 32)
202
                        | (static_cast<std::uint64_t>(n[7]) << 48));
203
    return {lo, hi};
204

205
}
206

207
bool isOutOfBounds(const R128 &b)
208
{
209
    constexpr std::uint64_t hi_threshold = UINT64_C(1) << 62;
210
    constexpr std::uint64_t lo_threshold = static_cast<std::uint64_t>(-static_cast<std::int64_t>(hi_threshold));
211
    return (b.hi > hi_threshold && b.hi < lo_threshold);
212
}
213

214
} // end namespace celestia::util
215