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.container.dynamic_array : DynamicArray;
63 	// alias Raw = DynamicArray!ubyte;
64 }
65 
66 pure nothrow @safe unittest {
67 	alias SInt = long;
68 	foreach (immutable i; 0 .. 64)
69 	{
70 		Raw os;
71 		os.encodeLEB128!SInt(i);
72 		assert(os.data.equal([i]));
73 		// const value = os.data.decodeLEB128!SInt();
74 	}
75 	foreach (immutable i; 64 .. 128)
76 	{
77 		Raw os;
78 		os.encodeLEB128!SInt(i);
79 		assert(os.data.equal([128 + i, 0]));
80 	}
81 }
82 
83 /// Encode a ULEB128 value to `os`.
84 void encodeULEB128(UInt, Output)(ref Output os, Unqual!UInt value)
85 	if (isOutputRange!(Output, ubyte) &&
86 		isUnsigned!UInt)
87 {
88 	do
89 	{
90 		ubyte byte_ = value & 0x7f;
91 		value >>= 7;
92 		if (value != 0)
93 			byte_ |= 0x80; // mark this byte to show that more bytes will follow
94 		os.put(char(byte_));
95 	}
96 	while (value != 0);
97 }
98 
99 /// Decode a ULEB128 value.
100 ulong decodeULEB128(ubyte *p, uint *n = null)
101 {
102 	const ubyte *orig_p = p;
103 	ulong value = 0;
104 	uint shift = 0;
105 	do
106 	{
107 		value += ulong(*p & 0x7f) << shift;
108 		shift += 7;
109 	}
110 	while (*p++ >= 128);
111 	if (n)
112 		*n = cast(uint)(p - orig_p);
113 	return value;
114 }
115 
116 pure nothrow @safe unittest {
117 	alias UInt = ulong;
118 	foreach (immutable i; 0 .. 128)
119 	{
120 		Raw os;
121 		os.encodeULEB128!UInt(i);
122 		assert(os.data.equal([i]));
123 	}
124 	foreach (immutable i; 128 .. 256)
125 	{
126 		Raw os;
127 		os.encodeULEB128!UInt(i);
128 		assert(os.data.equal([i, 1]));
129 	}
130 	foreach (immutable i; 256 .. 256 + 128)
131 	{
132 		Raw os;
133 		os.encodeULEB128!UInt(i);
134 		assert(os.data.equal([i - 128, 2]));
135 	}
136 	foreach (immutable i; 256 + 128 .. 512)
137 	{
138 		Raw os;
139 		os.encodeULEB128!UInt(i);
140 		assert(os.data.equal([i - 256, 3]));
141 	}
142 }
143 
144 /** Encode a ULEB128 value to a buffer.
145 	Returns: length in bytes of the encoded value.
146 */
147 uint encodeULEB128(ulong value, ubyte *p)
148 {
149 	ubyte *orig_p = p;
150 	do
151 	{
152 		ubyte byte_ = value & 0x7f;
153 		value >>= 7;
154 		if (value != 0)
155 			byte_ |= 0x80; // mark this byte to show that more bytes will follow
156 		*p++ = byte_;
157 	}
158 	while (value != 0);
159 	return cast(uint)(p - orig_p);
160 }