nxt.leb128 source code

1 /** LEB128 (Little Endian Base 128).
2 
3     See_Also: https://en.wikipedia.org/wiki/LEB128
4     See_Also: http://forum.dlang.org/post/ykskvwqdsxlyjispappj@forum.dlang.org
5 
6     TODO Move to Phobos at std/experimental/codings/leb128.d
7 */
8 module nxt.leb128;
9 
10 import std.range.primitives : isOutputRange;
11 import std.traits : isUnsigned, isSigned;
12 import core.internal.traits : Unqual;
13 
14 /// Encode a LEB128-encoded value of signed integer type `SInt` to `os`.
15 void encodeLEB128(SInt, Output)(ref Output os, Unqual!SInt value)
16     if (isOutputRange!(Output, ubyte) &&
17         isSigned!SInt)
18 {
19     bool more = false;
20     do
21     {
22         ubyte byte_ = value & 0x7f;
23         // assumes that this signed shift is an arithmetic right shift
24         value >>= 7;
25         more = !(((value == 0 ) && ((byte_ & 0x40) == 0)) ||
26                   ((value == -1) && ((byte_ & 0x40) != 0)));
27         if (more)
28             byte_ |= 0x80; // mark this byte to show that more bytes will follow
29         os.put(byte_);
30     }
31     while (more);
32 }
33 
34 /// Decode a LEB128-encoded value of signed integer type `SInt`.
35 SInt decodeLEB128(SInt)(ubyte *p, uint *n = null)
36 {
37     const ubyte *orig_p = p;
38     SInt value = 0;
39     uint shift = 0;
40     ubyte byte_;
41     do
42     {
43         byte_ = *p++;
44         value |= ((byte_ & 0x7f) << shift);
45         shift += 7;
46     } while (byte_ >= 128);
47     // sign extend negative numbers
48     if (byte_ & 0x40)
49         // TODO Unsigned!SInt
50         value |= (cast(ulong)-1) << shift; // value |= (-1ULL) << shift;
51     if (n)
52         *n = cast(uint)(p - orig_p);
53     return value;
54 }
55 
56 version(unittest)
57 {
58     import std.algorithm.comparison : equal;
59 
60     import std.array : Appender;
61     alias Raw = Appender!(ubyte[]);
62     // import nxt.dynamic_array : DynamicArray;
63     // alias Raw = DynamicArray!ubyte;
64 }
65 
66 @safe pure nothrow unittest
67 {
68     alias SInt = long;
69     foreach (immutable i; 0 .. 64)
70     {
71         Raw os;
72         os.encodeLEB128!SInt(i);
73         assert(os.data.equal([i]));
74         // const value = os.data.decodeLEB128!SInt();
75     }
76     foreach (immutable i; 64 .. 128)
77     {
78         Raw os;
79         os.encodeLEB128!SInt(i);
80         assert(os.data.equal([128 + i, 0]));
81     }
82 }
83 
84 /// Encode a ULEB128 value to `os`.
85 void encodeULEB128(UInt, Output)(ref Output os, Unqual!UInt value)
86     if (isOutputRange!(Output, ubyte) &&
87         isUnsigned!UInt)
88 {
89     do
90     {
91         ubyte byte_ = value & 0x7f;
92         value >>= 7;
93         if (value != 0)
94             byte_ |= 0x80; // mark this byte to show that more bytes will follow
95         os.put(char(byte_));
96     }
97     while (value != 0);
98 }
99 
100 /// Decode a ULEB128 value.
101 ulong decodeULEB128(ubyte *p, uint *n = null)
102 {
103     const ubyte *orig_p = p;
104     ulong value = 0;
105     uint shift = 0;
106     do
107     {
108         value += ulong(*p & 0x7f) << shift;
109         shift += 7;
110     }
111     while (*p++ >= 128);
112     if (n)
113         *n = cast(uint)(p - orig_p);
114     return value;
115 }
116 
117 @safe pure nothrow unittest
118 {
119     alias UInt = ulong;
120     foreach (immutable i; 0 .. 128)
121     {
122         Raw os;
123         os.encodeULEB128!UInt(i);
124         assert(os.data.equal([i]));
125     }
126     foreach (immutable i; 128 .. 256)
127     {
128         Raw os;
129         os.encodeULEB128!UInt(i);
130         assert(os.data.equal([i, 1]));
131     }
132     foreach (immutable i; 256 .. 256 + 128)
133     {
134         Raw os;
135         os.encodeULEB128!UInt(i);
136         assert(os.data.equal([i - 128, 2]));
137     }
138     foreach (immutable i; 256 + 128 .. 512)
139     {
140         Raw os;
141         os.encodeULEB128!UInt(i);
142         assert(os.data.equal([i - 256, 3]));
143     }
144 }
145 
146 /** Encode a ULEB128 value to a buffer.
147     Returns: length in bytes of the encoded value.
148 */
149 uint encodeULEB128(ulong value, ubyte *p)
150 {
151     ubyte *orig_p = p;
152     do
153     {
154         ubyte byte_ = value & 0x7f;
155         value >>= 7;
156         if (value != 0)
157             byte_ |= 0x80; // mark this byte to show that more bytes will follow
158         *p++ = byte_;
159     }
160     while (value != 0);
161     return cast(uint)(p - orig_p);
162 }