lib/simd/src/bitpack.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const memory = @import("memory.zig");
3 const shifts = @import("shift.zig");
4
5 pub const BlockPackingType = enum {
6 bit_packed,
7 frame_of_reference,
8 };
9
10 pub fn Pack8(comptime bits: usize) type {
11 validateBits(u8, bits);
12 return Packer(u8, bits);
13 }
14
15 pub fn Pack16(comptime bits: usize) type {
16 validateBits(u16, bits);
17 return Packer(u16, bits);
18 }
19
20 pub fn Pack32(comptime bits: usize) type {
21 validateBits(u32, bits);
22 return Packer(u32, bits);
23 }
24
25 pub fn Pack64(comptime bits: usize) type {
26 validateBits(u64, bits);
27 return Packer(u64, bits);
28 }
29
30 pub fn pack(
31 comptime D: type,
32 comptime bits: usize,
33 raw: []const D.Lane,
34 packed_output: []D.Lane,
35 ) void {
36 packBlock(D, bits, raw, packed_output, 0, .bit_packed);
37 }
38
39 pub fn unpack(
40 comptime D: type,
41 comptime bits: usize,
42 packed_input: []const D.Lane,
43 raw: []D.Lane,
44 ) void {
45 unpackBlock(D, bits, packed_input, raw, 0, .bit_packed);
46 }
47
48 pub fn packFrame(
49 comptime D: type,
50 comptime bits: usize,
51 raw: []const D.Lane,
52 packed_output: []D.Lane,
53 frame: D.Lane,
54 ) void {
55 requireFrameLane(D.Lane);
56 packBlock(D, bits, raw, packed_output, frame, .frame_of_reference);
57 }
58
59 pub fn unpackFrame(
60 comptime D: type,
61 comptime bits: usize,
62 packed_input: []const D.Lane,
63 raw: []D.Lane,
64 frame: D.Lane,
65 ) void {
66 requireFrameLane(D.Lane);
67 unpackBlock(D, bits, packed_input, raw, frame, .frame_of_reference);
68 }
69
70 fn Packer(comptime T: type, comptime bits: usize) type {
71 return struct {
72 pub fn pack(
73 _: @This(),
74 comptime D: type,
75 raw: []const T,
76 packed_output: []T,
77 ) void {
78 requireTag(D, T);
79 packBlock(D, bits, raw, packed_output, 0, .bit_packed);
80 }
81
82 pub fn unpack(
83 _: @This(),
84 comptime D: type,
85 packed_input: []const T,
86 raw: []T,
87 ) void {
88 requireTag(D, T);
89 unpackBlock(D, bits, packed_input, raw, 0, .bit_packed);
90 }
91
92 pub fn packFrame(
93 _: @This(),
94 comptime D: type,
95 raw: []const T,
96 packed_output: []T,
97 frame: T,
98 ) void {
99 requireTag(D, T);
100 requireFrameLane(T);
101 packBlock(D, bits, raw, packed_output, frame, .frame_of_reference);
102 }
103
104 pub fn unpackFrame(
105 _: @This(),
106 comptime D: type,
107 packed_input: []const T,
108 raw: []T,
109 frame: T,
110 ) void {
111 requireTag(D, T);
112 requireFrameLane(T);
113 unpackBlock(D, bits, packed_input, raw, frame, .frame_of_reference);
114 }
115 };
116 }
117
118 const layout8_1 =
119 "\x00\x01\x02\x03\x04\x05\x06\x07";
120
121 const layout8_2 =
122 "\x00\x01\x08\x09\x02\x03\x0A\x0B\x04\x05\x0C\x0D\x06\x07\x0E\x0F";
123
124 const layout8_3 =
125 "\x00\x01\x02\x08\x09\x0A\x10\x11\x12\x16\x17\x0E\x03\x04\x05\x0B\x0C\x0D" ++
126 "\x13\x14\x15\x0F\x06\x07";
127
128 const layout8_4 =
129 "\x00\x01\x02\x03\x08\x09\x0A\x0B\x04\x05\x06\x07\x0C\x0D\x0E\x0F\x10\x11" ++
130 "\x12\x13\x18\x19\x1A\x1B\x14\x15\x16\x17\x1C\x1D\x1E\x1F";
131
132 const layout8_5 =
133 "\x00\x01\x02\x03\x04\x08\x09\x0A\x0B\x0C\x10\x11\x12\x13\x14\x18\x19\x1A" ++
134 "\x1B\x1C\x20\x21\x05\x06\x07\x22\x23\x0D\x0E\x0F\x24\x25\x15\x16\x17\x26" ++
135 "\x27\x1D\x1E\x1F";
136
137 const layout8_6 =
138 "\x00\x01\x02\x03\x04\x05\x08\x09\x0A\x0B\x0C\x0D\x10\x11\x12\x13\x14\x15" ++
139 "\x16\x17\x0E\x0F\x06\x07\x18\x19\x1A\x1B\x1C\x1D\x20\x21\x22\x23\x24\x25" ++
140 "\x28\x29\x2A\x2B\x2C\x2D\x2E\x2F\x26\x27\x1E\x1F";
141
142 const layout8_7 =
143 "\x00\x01\x02\x03\x04\x05\x06\x08\x09\x0A\x0B\x0C\x0D\x0E\x10\x11\x12\x13" ++
144 "\x14\x15\x16\x18\x19\x1A\x1B\x1C\x1D\x1E\x20\x21\x22\x23\x24\x25\x26\x28" ++
145 "\x29\x2A\x2B\x2C\x2D\x2E\x30\x31\x32\x33\x34\x35\x36\x37\x2F\x27\x1F\x17" ++
146 "\x0F\x07";
147
148 const layout8_8 =
149 "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F\x10\x11" ++
150 "\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F\x20\x21\x22\x23" ++
151 "\x24\x25\x26\x27\x28\x29\x2A\x2B\x2C\x2D\x2E\x2F\x30\x31\x32\x33\x34\x35" ++
152 "\x36\x37\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F";
153
154 const layout16_1 =
155 "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F";
156
157 const layout16_2 =
158 "\x00\x01\x10\x11\x02\x03\x12\x13\x04\x05\x14\x15\x06\x07\x16\x17\x08\x09" ++
159 "\x18\x19\x0A\x0B\x1A\x1B\x0C\x0D\x1C\x1D\x0E\x0F\x1E\x1F";
160
161 const layout16_3 =
162 "\x00\x01\x02\x10\x11\x12\x20\x21\x22\x03\x04\x05\x13\x14\x15\x23\x24\x25" ++
163 "\x06\x07\x08\x16\x17\x18\x26\x27\x28\x09\x0A\x0B\x19\x1A\x1B\x29\x2A\x2B" ++
164 "\x0C\x0D\x0E\x1C\x1D\x1E\x2C\x2D\x2E\x0F\x1F\x2F";
165
166 const layout16_4 =
167 "\x00\x01\x02\x03\x10\x11\x12\x13\x04\x05\x06\x07\x14\x15\x16\x17\x08\x09" ++
168 "\x0A\x0B\x18\x19\x1A\x1B\x0C\x0D\x0E\x0F\x1C\x1D\x1E\x1F\x20\x21\x22\x23" ++
169 "\x30\x31\x32\x33\x24\x25\x26\x27\x34\x35\x36\x37\x28\x29\x2A\x2B\x38\x39" ++
170 "\x3A\x3B\x2C\x2D\x2E\x2F\x3C\x3D\x3E\x3F";
171
172 const layout16_5 =
173 "\x00\x01\x02\x03\x04\x10\x11\x12\x13\x14\x20\x21\x22\x23\x24\x30\x31\x32" ++
174 "\x33\x34\x40\x41\x42\x43\x44\x05\x06\x07\x08\x09\x15\x16\x17\x18\x19\x25" ++
175 "\x26\x27\x28\x29\x35\x36\x37\x38\x39\x45\x46\x47\x48\x49\x0A\x0B\x0C\x0D" ++
176 "\x0E\x1A\x1B\x1C\x1D\x1E\x2A\x2B\x2C\x2D\x2E\x3A\x3B\x3C\x3D\x3E\x4A\x4B" ++
177 "\x4C\x4D\x4E\x0F\x1F\x2F\x3F\x4F";
178
179 const layout16_6 =
180 "\x00\x01\x02\x03\x04\x05\x10\x11\x12\x13\x14\x15\x20\x21\x22\x23\x24\x25" ++
181 "\x0C\x0D\x0E\x0F\x1C\x1D\x06\x07\x08\x09\x0A\x0B\x16\x17\x18\x19\x1A\x1B" ++
182 "\x26\x27\x28\x29\x2A\x2B\x1E\x1F\x2C\x2D\x2E\x2F\x30\x31\x32\x33\x34\x35" ++
183 "\x40\x41\x42\x43\x44\x45\x50\x51\x52\x53\x54\x55\x3C\x3D\x3E\x3F\x4C\x4D" ++
184 "\x36\x37\x38\x39\x3A\x3B\x46\x47\x48\x49\x4A\x4B\x56\x57\x58\x59\x5A\x5B" ++
185 "\x4E\x4F\x5C\x5D\x5E\x5F";
186
187 const layout16_7 =
188 "\x00\x01\x02\x03\x04\x05\x06\x10\x11\x12\x13\x14\x15\x16\x20\x21\x22\x23" ++
189 "\x24\x25\x26\x30\x31\x32\x33\x34\x35\x36\x40\x41\x42\x43\x44\x45\x46\x50" ++
190 "\x51\x52\x53\x54\x55\x56\x60\x61\x62\x63\x64\x65\x66\x0E\x0F\x1E\x1F\x2E" ++
191 "\x2F\x3E\x07\x08\x09\x0A\x0B\x0C\x0D\x17\x18\x19\x1A\x1B\x1C\x1D\x27\x28" ++
192 "\x29\x2A\x2B\x2C\x2D\x37\x38\x39\x3A\x3B\x3C\x3D\x47\x48\x49\x4A\x4B\x4C" ++
193 "\x4D\x57\x58\x59\x5A\x5B\x5C\x5D\x67\x68\x69\x6A\x6B\x6C\x6D\x3F\x4E\x4F" ++
194 "\x5E\x5F\x6E\x6F";
195
196 const layout16_8 =
197 "\x00\x01\x02\x03\x04\x05\x06\x07\x10\x11\x12\x13\x14\x15\x16\x17\x08\x09" ++
198 "\x0A\x0B\x0C\x0D\x0E\x0F\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F\x20\x21\x22\x23" ++
199 "\x24\x25\x26\x27\x30\x31\x32\x33\x34\x35\x36\x37\x28\x29\x2A\x2B\x2C\x2D" ++
200 "\x2E\x2F\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F\x40\x41\x42\x43\x44\x45\x46\x47" ++
201 "\x50\x51\x52\x53\x54\x55\x56\x57\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F\x58\x59" ++
202 "\x5A\x5B\x5C\x5D\x5E\x5F\x60\x61\x62\x63\x64\x65\x66\x67\x70\x71\x72\x73" ++
203 "\x74\x75\x76\x77\x68\x69\x6A\x6B\x6C\x6D\x6E\x6F\x78\x79\x7A\x7B\x7C\x7D" ++
204 "\x7E\x7F";
205
206 const layout16_9 =
207 "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x10\x11\x12\x13\x14\x15\x16\x17\x18" ++
208 "\x20\x21\x22\x23\x24\x25\x26\x27\x28\x30\x31\x32\x33\x34\x35\x36\x37\x38" ++
209 "\x40\x41\x42\x43\x44\x45\x46\x47\x48\x50\x51\x52\x53\x54\x55\x56\x57\x58" ++
210 "\x60\x61\x62\x63\x64\x65\x66\x67\x68\x70\x71\x72\x73\x74\x75\x76\x77\x78" ++
211 "\x09\x0A\x0B\x0C\x0D\x0E\x0F\x80\x81\x19\x1A\x1B\x1C\x1D\x1E\x1F\x82\x83" ++
212 "\x29\x2A\x2B\x2C\x2D\x2E\x2F\x84\x85\x39\x3A\x3B\x3C\x3D\x3E\x3F\x86\x87" ++
213 "\x49\x4A\x4B\x4C\x4D\x4E\x4F\x88\x89\x59\x5A\x5B\x5C\x5D\x5E\x5F\x8A\x8B" ++
214 "\x69\x6A\x6B\x6C\x6D\x6E\x6F\x8C\x8D\x79\x7A\x7B\x7C\x7D\x7E\x7F\x8E\x8F";
215
216 const layout16_10 =
217 "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x10\x11\x12\x13\x14\x15\x16\x17" ++
218 "\x18\x19\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x30\x31\x32\x33\x34\x35" ++
219 "\x36\x37\x38\x39\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x50\x51\x52\x53" ++
220 "\x54\x55\x56\x57\x58\x59\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x70\x71" ++
221 "\x72\x73\x74\x75\x76\x77\x78\x79\x0A\x0B\x0C\x0D\x0E\x0F\x80\x81\x82\x83" ++
222 "\x1A\x1B\x1C\x1D\x1E\x1F\x84\x85\x86\x87\x2A\x2B\x2C\x2D\x2E\x2F\x88\x89" ++
223 "\x8A\x8B\x3A\x3B\x3C\x3D\x3E\x3F\x8C\x8D\x8E\x8F\x4A\x4B\x4C\x4D\x4E\x4F" ++
224 "\x90\x91\x92\x93\x5A\x5B\x5C\x5D\x5E\x5F\x94\x95\x96\x97\x6A\x6B\x6C\x6D" ++
225 "\x6E\x6F\x98\x99\x9A\x9B\x7A\x7B\x7C\x7D\x7E\x7F\x9C\x9D\x9E\x9F";
226
227 const layout16_11 =
228 "\x00\x01\x02\x03\x04\x05\x06\x07\x80\x81\x82\x08\x09\x0A\x0B\x0C\x0D\x0E" ++
229 "\x0F\x90\x91\x92\x10\x11\x12\x13\x14\x15\x16\x17\xA0\xA1\xA2\x18\x19\x1A" ++
230 "\x1B\x1C\x1D\x1E\x1F\x83\x84\x85\x20\x21\x22\x23\x24\x25\x26\x27\x93\x94" ++
231 "\x95\x28\x29\x2A\x2B\x2C\x2D\x2E\x2F\xA3\xA4\xA5\x30\x31\x32\x33\x34\x35" ++
232 "\x36\x37\x86\x87\x88\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F\x96\x97\x98\x40\x41" ++
233 "\x42\x43\x44\x45\x46\x47\xA6\xA7\xA8\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F\x89" ++
234 "\x8A\x8B\x50\x51\x52\x53\x54\x55\x56\x57\x99\x9A\x9B\x58\x59\x5A\x5B\x5C" ++
235 "\x5D\x5E\x5F\xA9\xAA\xAB\x60\x61\x62\x63\x64\x65\x66\x67\x8C\x8D\x8E\x68" ++
236 "\x69\x6A\x6B\x6C\x6D\x6E\x6F\x9C\x9D\x9E\x70\x71\x72\x73\x74\x75\x76\x77" ++
237 "\xAC\xAD\xAE\x78\x79\x7A\x7B\x7C\x7D\x7E\x7F\x8F\x9F\xAF";
238
239 const layout16_12 =
240 "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x10\x11\x12\x13\x14\x15" ++
241 "\x16\x17\x18\x19\x1A\x1B\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2A\x2B" ++
242 "\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3A\x3B\x40\x41\x42\x43\x44\x45" ++
243 "\x46\x47\x48\x49\x4A\x4B\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5A\x5B" ++
244 "\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6A\x6B\x70\x71\x72\x73\x74\x75" ++
245 "\x76\x77\x78\x79\x7A\x7B\x0C\x0D\x0E\x0F\x80\x81\x82\x83\x84\x85\x86\x87" ++
246 "\x1C\x1D\x1E\x1F\x88\x89\x8A\x8B\x8C\x8D\x8E\x8F\x2C\x2D\x2E\x2F\x90\x91" ++
247 "\x92\x93\x94\x95\x96\x97\x3C\x3D\x3E\x3F\x98\x99\x9A\x9B\x9C\x9D\x9E\x9F" ++
248 "\x4C\x4D\x4E\x4F\xA0\xA1\xA2\xA3\xA4\xA5\xA6\xA7\x5C\x5D\x5E\x5F\xA8\xA9" ++
249 "\xAA\xAB\xAC\xAD\xAE\xAF\x6C\x6D\x6E\x6F\xB0\xB1\xB2\xB3\xB4\xB5\xB6\xB7" ++
250 "\x7C\x7D\x7E\x7F\xB8\xB9\xBA\xBB\xBC\xBD\xBE\xBF";
251
252 const layout16_13 =
253 "\x00\x01\x02\x03\x04\x05\x06\x07\x80\x81\x82\x83\x84\x08\x09\x0A\x0B\x0C" ++
254 "\x0D\x0E\x0F\x90\x91\x92\x93\x94\x10\x11\x12\x13\x14\x15\x16\x17\xA0\xA1" ++
255 "\xA2\xA3\xA4\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F\xB0\xB1\xB2\xB3\xB4\x20\x21" ++
256 "\x22\x23\x24\x25\x26\x27\xC0\xC1\xC2\xC3\xC4\x28\x29\x2A\x2B\x2C\x2D\x2E" ++
257 "\x2F\x85\x86\x87\x88\x89\x30\x31\x32\x33\x34\x35\x36\x37\x95\x96\x97\x98" ++
258 "\x99\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F\xA5\xA6\xA7\xA8\xA9\x40\x41\x42\x43" ++
259 "\x44\x45\x46\x47\xB5\xB6\xB7\xB8\xB9\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F\xC5" ++
260 "\xC6\xC7\xC8\xC9\x50\x51\x52\x53\x54\x55\x56\x57\x8A\x8B\x8C\x8D\x8E\x58" ++
261 "\x59\x5A\x5B\x5C\x5D\x5E\x5F\x9A\x9B\x9C\x9D\x9E\x60\x61\x62\x63\x64\x65" ++
262 "\x66\x67\xAA\xAB\xAC\xAD\xAE\x68\x69\x6A\x6B\x6C\x6D\x6E\x6F\xBA\xBB\xBC" ++
263 "\xBD\xBE\x70\x71\x72\x73\x74\x75\x76\x77\xCA\xCB\xCC\xCD\xCE\x78\x79\x7A" ++
264 "\x7B\x7C\x7D\x7E\x7F\x8F\x9F\xAF\xBF\xCF";
265
266 const layout16_14 =
267 "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x10\x11\x12\x13" ++
268 "\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x20\x21\x22\x23\x24\x25\x26\x27" ++
269 "\x28\x29\x2A\x2B\x2C\x2D\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3A\x3B" ++
270 "\x3C\x3D\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4A\x4B\x4C\x4D\x50\x51" ++
271 "\x52\x53\x54\x55\x56\x57\x58\x59\x5A\x5B\x5C\x5D\x60\x61\x62\x63\x64\x65" ++
272 "\x66\x67\x68\x69\x6A\x6B\x6C\x6D\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79" ++
273 "\x7A\x7B\x7C\x7D\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8A\x8B\x8C\x8D" ++
274 "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9A\x9B\x9C\x9D\xA0\xA1\xA2\xA3" ++
275 "\xA4\xA5\xA6\xA7\xA8\xA9\xAA\xAB\xAC\xAD\xB0\xB1\xB2\xB3\xB4\xB5\xB6\xB7" ++
276 "\xB8\xB9\xBA\xBB\xBC\xBD\xC0\xC1\xC2\xC3\xC4\xC5\xC6\xC7\xC8\xC9\xCA\xCB" ++
277 "\xCC\xCD\xD0\xD1\xD2\xD3\xD4\xD5\xD6\xD7\xD8\xD9\xDA\xDB\xDC\xDD\x0E\x0F" ++
278 "\x1E\x1F\x2E\x2F\x3E\x3F\x4E\x4F\x5E\x5F\x6E\x6F\x7E\x7F\x8E\x8F\x9E\x9F" ++
279 "\xAE\xAF\xBE\xBF\xCE\xCF\xDE\xDF";
280
281 const layout16_15 =
282 "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x10\x11\x12" ++
283 "\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x20\x21\x22\x23\x24\x25" ++
284 "\x26\x27\x28\x29\x2A\x2B\x2C\x2D\x2E\x30\x31\x32\x33\x34\x35\x36\x37\x38" ++
285 "\x39\x3A\x3B\x3C\x3D\x3E\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4A\x4B" ++
286 "\x4C\x4D\x4E\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5A\x5B\x5C\x5D\x5E" ++
287 "\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6A\x6B\x6C\x6D\x6E\x70\x71\x72" ++
288 "\x73\x74\x75\x76\x77\x78\x79\x7A\x7B\x7C\x7D\x7E\x80\x81\x82\x83\x84\x85" ++
289 "\x86\x87\x88\x89\x8A\x8B\x8C\x8D\x8E\x90\x91\x92\x93\x94\x95\x96\x97\x98" ++
290 "\x99\x9A\x9B\x9C\x9D\x9E\xA0\xA1\xA2\xA3\xA4\xA5\xA6\xA7\xA8\xA9\xAA\xAB" ++
291 "\xAC\xAD\xAE\xB0\xB1\xB2\xB3\xB4\xB5\xB6\xB7\xB8\xB9\xBA\xBB\xBC\xBD\xBE" ++
292 "\xC0\xC1\xC2\xC3\xC4\xC5\xC6\xC7\xC8\xC9\xCA\xCB\xCC\xCD\xCE\xD0\xD1\xD2" ++
293 "\xD3\xD4\xD5\xD6\xD7\xD8\xD9\xDA\xDB\xDC\xDD\xDE\xE0\xE1\xE2\xE3\xE4\xE5" ++
294 "\xE6\xE7\xE8\xE9\xEA\xEB\xEC\xED\xEE\x0F\x1F\x2F\x3F\x4F\x5F\x6F\x7F\x8F" ++
295 "\x9F\xAF\xBF\xCF\xDF\xEF";
296
297 const layout16_16 =
298 "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0A\x0B\x0C\x0D\x0E\x0F\x10\x11" ++
299 "\x12\x13\x14\x15\x16\x17\x18\x19\x1A\x1B\x1C\x1D\x1E\x1F\x20\x21\x22\x23" ++
300 "\x24\x25\x26\x27\x28\x29\x2A\x2B\x2C\x2D\x2E\x2F\x30\x31\x32\x33\x34\x35" ++
301 "\x36\x37\x38\x39\x3A\x3B\x3C\x3D\x3E\x3F\x40\x41\x42\x43\x44\x45\x46\x47" ++
302 "\x48\x49\x4A\x4B\x4C\x4D\x4E\x4F\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59" ++
303 "\x5A\x5B\x5C\x5D\x5E\x5F\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6A\x6B" ++
304 "\x6C\x6D\x6E\x6F\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7A\x7B\x7C\x7D" ++
305 "\x7E\x7F\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8A\x8B\x8C\x8D\x8E\x8F" ++
306 "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9A\x9B\x9C\x9D\x9E\x9F\xA0\xA1" ++
307 "\xA2\xA3\xA4\xA5\xA6\xA7\xA8\xA9\xAA\xAB\xAC\xAD\xAE\xAF\xB0\xB1\xB2\xB3" ++
308 "\xB4\xB5\xB6\xB7\xB8\xB9\xBA\xBB\xBC\xBD\xBE\xBF\xC0\xC1\xC2\xC3\xC4\xC5" ++
309 "\xC6\xC7\xC8\xC9\xCA\xCB\xCC\xCD\xCE\xCF\xD0\xD1\xD2\xD3\xD4\xD5\xD6\xD7" ++
310 "\xD8\xD9\xDA\xDB\xDC\xDD\xDE\xDF\xE0\xE1\xE2\xE3\xE4\xE5\xE6\xE7\xE8\xE9" ++
311 "\xEA\xEB\xEC\xED\xEE\xEF\xF0\xF1\xF2\xF3\xF4\xF5\xF6\xF7\xF8\xF9\xFA\xFB" ++
312 "\xFC\xFD\xFE\xFF";
313
314 fn specializedLayout(comptime T: type, comptime bits: usize) []const u8 {
315 if (T == u8) return switch (bits) {
316 1 => layout8_1,
317 2 => layout8_2,
318 3 => layout8_3,
319 4 => layout8_4,
320 5 => layout8_5,
321 6 => layout8_6,
322 7 => layout8_7,
323 8 => layout8_8,
324 else => unreachable,
325 };
326 if (T == u16) return switch (bits) {
327 1 => layout16_1,
328 2 => layout16_2,
329 3 => layout16_3,
330 4 => layout16_4,
331 5 => layout16_5,
332 6 => layout16_6,
333 7 => layout16_7,
334 8 => layout16_8,
335 9 => layout16_9,
336 10 => layout16_10,
337 11 => layout16_11,
338 12 => layout16_12,
339 13 => layout16_13,
340 14 => layout16_14,
341 15 => layout16_15,
342 16 => layout16_16,
343 else => unreachable,
344 };
345 unreachable;
346 }
347
348 fn packBlock(
349 comptime D: type,
350 comptime bits: usize,
351 raw: []const D.Lane,
352 packed_output: []D.Lane,
353 frame: D.Lane,
354 comptime packing_type: BlockPackingType,
355 ) void {
356 validateBits(D.Lane, bits);
357 const lane_bits = @bitSizeOf(D.Lane);
358 const raw_count = lane_bits * D.lane_count;
359 const packed_count = bits * D.lane_count;
360 std.debug.assert(raw.len >= raw_count);
361 std.debug.assert(packed_output.len >= packed_count);
362 if (D.Lane == u8 or D.Lane == u16) {
363 packSpecialized(D, bits, raw, packed_output, frame, packing_type);
364 return;
365 }
366 @memset(packed_output[0..packed_count], 0);
367 const value_mask = mask(D.Lane, bits);
368
369 var raw_position: usize = 0;
370 while (raw_position < lane_bits) : (raw_position += 1) {
371 const bit_position = raw_position * bits;
372 const packed_position = bit_position / lane_bits;
373 const shift = bit_position % lane_bits;
374 var lane_index: usize = 0;
375 while (lane_index < D.lane_count) : (lane_index += 1) {
376 const raw_value = raw[raw_position * D.lane_count + lane_index];
377 const delta = if (packing_type == .frame_of_reference)
378 raw_value -% frame
379 else
380 raw_value;
381 const value = delta & value_mask;
382 packed_output[packed_position * D.lane_count + lane_index] |= value << @intCast(shift);
383 if (shift + bits > lane_bits) {
384 packed_output[(packed_position + 1) * D.lane_count + lane_index] |=
385 value >> @intCast(lane_bits - shift);
386 }
387 }
388 }
389 }
390
391 fn unpackBlock(
392 comptime D: type,
393 comptime bits: usize,
394 packed_input: []const D.Lane,
395 raw: []D.Lane,
396 frame: D.Lane,
397 comptime packing_type: BlockPackingType,
398 ) void {
399 validateBits(D.Lane, bits);
400 const lane_bits = @bitSizeOf(D.Lane);
401 const raw_count = lane_bits * D.lane_count;
402 const packed_count = bits * D.lane_count;
403 std.debug.assert(packed_input.len >= packed_count);
404 std.debug.assert(raw.len >= raw_count);
405 if (D.Lane == u8 or D.Lane == u16) {
406 unpackSpecialized(D, bits, packed_input, raw, frame, packing_type);
407 return;
408 }
409 const value_mask = mask(D.Lane, bits);
410
411 var raw_position: usize = 0;
412 while (raw_position < lane_bits) : (raw_position += 1) {
413 const bit_position = raw_position * bits;
414 const packed_position = bit_position / lane_bits;
415 const shift = bit_position % lane_bits;
416 var lane_index: usize = 0;
417 while (lane_index < D.lane_count) : (lane_index += 1) {
418 var value = packed_input[packed_position * D.lane_count + lane_index] >>
419 @intCast(shift);
420 if (shift + bits > lane_bits) {
421 value |= packed_input[(packed_position + 1) * D.lane_count + lane_index] <<
422 @intCast(lane_bits - shift);
423 }
424 value &= value_mask;
425 raw[raw_position * D.lane_count + lane_index] = if (packing_type == .frame_of_reference)
426 value +% frame
427 else
428 value;
429 }
430 }
431 }
432
433 fn packSpecialized(
434 comptime D: type,
435 comptime bits: usize,
436 raw: []const D.Lane,
437 packed_output: []D.Lane,
438 frame: D.Lane,
439 comptime packing_type: BlockPackingType,
440 ) void {
441 const lane_bits = @bitSizeOf(D.Lane);
442 const layout = comptime specializedLayout(D.Lane, bits);
443 const one: D.Vector = @splat(1);
444 const frame_vector: D.Vector = @splat(frame);
445 var packed_vectors: [bits]D.Vector = undefined;
446 inline for (0..bits) |packed_position| packed_vectors[packed_position] = @splat(0);
447 inline for (0..lane_bits) |raw_position| {
448 const loaded = memory.load(D, raw[raw_position * D.lane_count ..]);
449 const value = if (packing_type == .frame_of_reference) loaded -% frame_vector else loaded;
450 inline for (0..bits) |raw_bit| {
451 const target = comptime layout[raw_position * bits + raw_bit];
452 const packed_position = target / lane_bits;
453 const packed_bit = target % lane_bits;
454 const source_bit = shifts.shiftRight(D, raw_bit, value) & one;
455 packed_vectors[packed_position] |= shifts.shiftLeft(D, packed_bit, source_bit);
456 }
457 }
458 inline for (0..bits) |packed_position| {
459 memory.store(
460 D,
461 packed_vectors[packed_position],
462 packed_output[packed_position * D.lane_count ..],
463 );
464 }
465 }
466
467 fn unpackSpecialized(
468 comptime D: type,
469 comptime bits: usize,
470 packed_input: []const D.Lane,
471 raw: []D.Lane,
472 frame: D.Lane,
473 comptime packing_type: BlockPackingType,
474 ) void {
475 const lane_bits = @bitSizeOf(D.Lane);
476 const layout = comptime specializedLayout(D.Lane, bits);
477 const one: D.Vector = @splat(1);
478 const frame_vector: D.Vector = @splat(frame);
479 var packed_vectors: [bits]D.Vector = undefined;
480 inline for (0..bits) |packed_position| {
481 packed_vectors[packed_position] = memory.load(
482 D,
483 packed_input[packed_position * D.lane_count ..],
484 );
485 }
486 inline for (0..lane_bits) |raw_position| {
487 var value: D.Vector = @splat(0);
488 inline for (0..bits) |raw_bit| {
489 const target = comptime layout[raw_position * bits + raw_bit];
490 const packed_position = target / lane_bits;
491 const packed_bit = target % lane_bits;
492 const source_bit = shifts.shiftRight(
493 D,
494 packed_bit,
495 packed_vectors[packed_position],
496 ) & one;
497 value |= shifts.shiftLeft(D, raw_bit, source_bit);
498 }
499 if (packing_type == .frame_of_reference) value +%= frame_vector;
500 memory.store(D, value, raw[raw_position * D.lane_count ..]);
501 }
502 }
503
504 fn mask(comptime T: type, comptime bits: usize) T {
505 return if (bits == @bitSizeOf(T))
506 std.math.maxInt(T)
507 else
508 (@as(T, 1) << @intCast(bits)) - 1;
509 }
510
511 fn validateBits(comptime T: type, comptime bits: usize) void {
512 if (T != u8 and T != u16 and T != u32 and T != u64) {
513 @compileError("bit packing requires unsigned 8/16/32/64-bit lanes");
514 }
515 if (bits == 0 or bits > @bitSizeOf(T)) {
516 @compileError("bit width must be between one and the lane width");
517 }
518 }
519
520 fn requireFrameLane(comptime T: type) void {
521 if (T != u32 and T != u64) {
522 @compileError("frame-of-reference packing requires u32 or u64 lanes");
523 }
524 }
525
526 fn requireTag(comptime D: type, comptime T: type) void {
527 if (D.Lane != T) @compileError("packer lane type does not match the SIMD descriptor");
528 }
529
530 const oracle_hash_u8 = [_]u64{
531 0x445918642857068F, 0xA2E4FE0A8A14645B, 0x952FDA26DE4D792F, 0xB7BF9F362C0CC2B3,
532 0x888934B9B5BC81FF, 0xDF7BF05E7FDCE12B, 0x344B817F42FBD8FF, 0x588B57EFBE2BAE23,
533 };
534
535 const oracle_hash_u16 = [_]u64{
536 0x412F38E60A3CD08F, 0xEF96D0ABD29EC45B, 0x627759D35900D62F, 0xFA781CA1B06284B3,
537 0xBD4F00CB3F53D547, 0x98A63232BE8E75AB, 0xA903B5A48D192C7F, 0xA230A9F866EE8BE3,
538 0x018616763CCB1757, 0xEACDF92E97167616, 0x06AC8D9059C57FB8, 0xB86437886F0F9903,
539 0x67977F03A663B6F1, 0x5647B715CFAFCAAB, 0x69A4F125B793851F, 0x4B37C2B78CCFC343,
540 };
541
542 const oracle_hash_u32 = [_]u64{
543 0xB3354FB2D7F2D08F, 0x42F087AE2A9CC45B, 0x5972FCB2F9794613, 0xED03FC46532B8AB3,
544 0x84A0BFE381C2F757, 0xF018D415C434DB43, 0x2443042D91E8E0B3, 0x6D41781B4610E063,
545 0x9BE0E3E300DD518E, 0xA613F8C73B542DB2, 0xF8AEF7BBAE35BEE9, 0x8F92C8F960FA27A9,
546 0x60A6BDEF4DE3FA67, 0x667E2E78D4CADAB1, 0xD8498FA419F8BF52, 0xC559A5FE19F318C3,
547 0x8F8EA26B41F6016B, 0x88E6559D50D10263, 0x8EFBC2B179E4694D, 0xF83B77CDF5854777,
548 0x4B83773A8F52DE0D, 0x682957C60438F230, 0x60353F206E4FFE71, 0xB20962337FD39C41,
549 0x0673EB84C964F944, 0xA3CFBEBF7C61193D, 0x3A4F9B326F105DD9, 0xF4EB6C89143E37C8,
550 0x38F4AB6AD8D682F1, 0xF324F956F06F8E01, 0xB992364C045D5303, 0x3FDA92E7E83F9F03,
551 };
552
553 const oracle_hash_u64 = [_]u64{
554 0xC8A8DCA8D7F2D08F, 0x08E2700E2A9CC45B, 0x37EABE436B850113, 0x79F5332A532B8AB3,
555 0xDB591C66FD7121F7, 0x94E4C2AE06E22A93, 0x14210EB8EFF3E75B, 0xEFC6FF814A51DFE3,
556 0xDA72BC45D3E32E94, 0xF5AA2A9F19B60B3C, 0x2B181B3B80DBBAA2, 0xE63B8A505E8A3462,
557 0x44201D6A24AAE5B7, 0x2CF59E306D441E61, 0x94D9A488800573CD, 0xFF891666E4767643,
558 0x04168531C674F955, 0x7D27C1DB1380D32F, 0x0CCAC46C02118B7F, 0xD60AFE3159F79979,
559 0x99F8EE3C99B6BD2F, 0x649BEC6B0E0136FE, 0x9CECEEA047198D7F, 0x86A2E33909530A0A,
560 0xB2865857B6E3EEEB, 0x165969A6F121AC62, 0x5511C1396CE42712, 0x694E2CCA74020E5A,
561 0x544456B8F9B097F4, 0x9DB5804D02E2CA3D, 0x83D888FE728BEDD6, 0xE4B8A887810A4503,
562 0xFFC2C812130D501C, 0x0ED2A63580423C5C, 0x54E3235B193C65F9, 0x2B37B16E74E37DF8,
563 0xAAB1D0697C96DC1A, 0x83D31DFEE1812CB8, 0xE6949409F6ED05D7, 0xAB437BF1CBDE0730,
564 0x6C8955286D33AFF4, 0x6E097DF511FA164D, 0x038FCCD2E9080CE9, 0xBF7E70C7ECB2908F,
565 0x993D69BA5CC7E02D, 0xA80588E548FA85AD, 0xE6D63E9C95655C29, 0xCD938593440CA85F,
566 0xBB6E36D2BAE57E0C, 0x10D328E57C2058F3, 0x306B03883B04466D, 0x8907055B3577A03C,
567 0xF3A6156D447F76B5, 0x477FF22DD2B46117, 0x3DE2513B9F77B864, 0x0669522BED043B13,
568 0x772E5DB310C890B4, 0x567A883C61807F42, 0x8A7252BA46FD7A70, 0xD45002AE6C337D49,
569 0x13EDD158B3AD5098, 0x9E693F0D7EE3B312, 0x9CFB0C5BAA6CE324, 0xE867F97A86993A83,
570 };
571
572 fn hashPacked(comptime T: type, values: []const T) u64 {
573 var hash: u64 = 1469598103934665603;
574 for (values) |value| {
575 hash ^= @as(u64, value);
576 hash *%= 1099511628211;
577 }
578 return hash;
579 }
580
581 fn verifyOracleHash(comptime T: type, comptime bits: usize, expected: u64) !void {
582 const simd = @import("root.zig");
583 const D = simd.FixedTag(T, 4);
584 const lane_bits = @bitSizeOf(T);
585 const raw_count = lane_bits * D.lane_count;
586 const packed_count = bits * D.lane_count;
587 const value_mask = mask(T, bits);
588 var raw: [raw_count]T = undefined;
589 var packed_values: [packed_count]T = undefined;
590 for (&raw, 0..) |*value, index| {
591 const i: u64 = @intCast(index);
592 const mixed = (i *% 0x9E37_79B9_7F4A_7C15) ^
593 ((i +% 0x51) *% 0xD1B5_4A32_D192_ED03);
594 value.* = @as(T, @truncate(mixed)) & value_mask;
595 }
596 const P = switch (T) {
597 u8 => Pack8(bits),
598 u16 => Pack16(bits),
599 u32 => Pack32(bits),
600 u64 => Pack64(bits),
601 else => unreachable,
602 };
603 (P{}).pack(D, &raw, &packed_values);
604 try std.testing.expectEqual(expected, hashPacked(T, &packed_values));
605 if (T == u32 or T == u64) {
606 const frame: T = @truncate(0x1020_3040_5060_7080);
607 for (&raw, 0..) |*value, index| {
608 const i: u64 = @intCast(index);
609 const mixed = (i *% 0x9E37_79B9_7F4A_7C15) ^
610 ((i +% 0x51) *% 0xD1B5_4A32_D192_ED03);
611 value.* = frame +% (@as(T, @truncate(mixed)) & value_mask);
612 }
613 (P{}).packFrame(D, &raw, &packed_values, frame);
614 try std.testing.expectEqual(expected, hashPacked(T, &packed_values));
615 }
616 }
617
618 fn verifyRoundTrip(comptime T: type, comptime bits: usize) !void {
619 const simd = @import("root.zig");
620 const D = simd.FixedTag(T, 4);
621 const lane_bits = @bitSizeOf(T);
622 const raw_count = lane_bits * D.lane_count;
623 const packed_count = bits * D.lane_count;
624 const value_mask = mask(T, bits);
625 var raw: [raw_count]T = undefined;
626 var restored: [raw_count]T = undefined;
627 var packed_values: [packed_count]T = undefined;
628 for (&raw, 0..) |*value, index| {
629 const mixed = @as(T, @truncate(index *% 0x9e37 +% 0x51)) ^
630 @as(T, @truncate(index >> 1));
631 value.* = mixed & value_mask;
632 }
633
634 const P = switch (T) {
635 u8 => Pack8(bits),
636 u16 => Pack16(bits),
637 u32 => Pack32(bits),
638 u64 => Pack64(bits),
639 else => unreachable,
640 };
641 (P{}).pack(D, &raw, &packed_values);
642 (P{}).unpack(D, &packed_values, &restored);
643 try std.testing.expectEqualSlices(T, &raw, &restored);
644 }
645
646 fn verifyFrameRoundTrip(comptime T: type, comptime bits: usize) !void {
647 const simd = @import("root.zig");
648 const D = simd.FixedTag(T, 4);
649 const lane_bits = @bitSizeOf(T);
650 const raw_count = lane_bits * D.lane_count;
651 const packed_count = bits * D.lane_count;
652 const value_mask = mask(T, bits);
653 const frame: T = 0x1020_3040;
654 var raw: [raw_count]T = undefined;
655 var restored: [raw_count]T = undefined;
656 var packed_values: [packed_count]T = undefined;
657 for (&raw, 0..) |*value, index| {
658 const delta = (@as(T, @truncate(index *% 0x9e37 +% 0x51))) & value_mask;
659 value.* = frame +% delta;
660 }
661
662 const P = if (T == u32) Pack32(bits) else Pack64(bits);
663 (P{}).packFrame(D, &raw, &packed_values, frame);
664 (P{}).unpackFrame(D, &packed_values, &restored, frame);
665 try std.testing.expectEqualSlices(T, &raw, &restored);
666 }
667
668 test "Highway bit pack round trips every Pack8 and Pack16 width" {
669 inline for (1..9) |bits| try verifyRoundTrip(u8, bits);
670 inline for (1..17) |bits| try verifyRoundTrip(u16, bits);
671 }
672
673 test "Highway bit pack round trips every Pack32 and Pack64 width" {
674 inline for (1..33) |bits| try verifyRoundTrip(u32, bits);
675 inline for (1..65) |bits| try verifyRoundTrip(u64, bits);
676 }
677
678 test "Highway frame-of-reference packing round trips every wide width" {
679 inline for (1..33) |bits| try verifyFrameRoundTrip(u32, bits);
680 inline for (1..65) |bits| try verifyFrameRoundTrip(u64, bits);
681 }
682
683 test "Highway packed output matches the pinned implementation at every width" {
684 inline for (1..9) |bits| try verifyOracleHash(u8, bits, oracle_hash_u8[bits - 1]);
685 inline for (1..17) |bits| try verifyOracleHash(u16, bits, oracle_hash_u16[bits - 1]);
686 inline for (1..33) |bits| try verifyOracleHash(u32, bits, oracle_hash_u32[bits - 1]);
687 inline for (1..65) |bits| try verifyOracleHash(u64, bits, oracle_hash_u64[bits - 1]);
688 }
689
690 test "Highway specialized layouts are complete bit permutations" {
691 inline for (.{ u8, u16 }) |T| {
692 inline for (1..@bitSizeOf(T) + 1) |bits| {
693 const layout = specializedLayout(T, bits);
694 var seen: [@bitSizeOf(T) * bits]bool = @splat(false);
695 for (layout) |target| {
696 try std.testing.expect(target < seen.len);
697 try std.testing.expect(!seen[target]);
698 seen[target] = true;
699 }
700 for (seen) |present| try std.testing.expect(present);
701 }
702 }
703 }
704
705 test "Highway Pack8 layout matches the pinned implementation" {
706 const simd = @import("root.zig");
707 const D = simd.FixedTag(u8, 4);
708 var raw: [8 * D.lane_count]u8 = undefined;
709 for (0..8) |position| {
710 for (0..D.lane_count) |lane_index| {
711 raw[position * D.lane_count + lane_index] = @truncate((position + lane_index) & 7);
712 }
713 }
714 var packed_values: [3 * D.lane_count]u8 = undefined;
715 (Pack8(3){}).pack(D, &raw, &packed_values);
716 try std.testing.expectEqualSlices(u8, &.{ 0xE0, 0x29, 0x32, 0x7B }, packed_values[0..4]);
717 try std.testing.expectEqualSlices(u8, &.{ 0xA9, 0x72, 0xFB, 0x44 }, packed_values[4..8]);
718 try std.testing.expectEqualSlices(u8, &.{ 0xF2, 0x3B, 0x44, 0x8D }, packed_values[8..12]);
719 }