1 // Univariate Polynomials over the ring GF(2) = Z/2Z.
3 #include "cl_GV_modinteger.h"
4 #include "cl_modinteger.h"
5 #include "cl_GV_integer.h"
10 // This is actually defined in cl_GV_I.cc (*ugh*).
11 struct cl_heap_GV_I_bits1 : public cl_heap_GV_I {
15 static cl_boolean gf2_equal (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y)
17 DeclarePoly(cl_GV_MI,x);
18 DeclarePoly(cl_GV_MI,y);
20 var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
21 var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer;
22 var uintL xlen = xv->v.length();
23 var uintL ylen = yv->v.length();
26 // We can compare full words since unused bits in the last word are 0.
27 var uintL count = ceiling(xlen,intDsize);
28 if (compare_loop_up(xv->data,yv->data,count) != 0)
33 static const _cl_UP gf2_plus (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y)
35 DeclarePoly(cl_GV_MI,x);
36 DeclarePoly(cl_GV_MI,y);
37 var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
38 var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer;
39 var uintL xlen = xv->v.length();
40 var uintL ylen = yv->v.length();
42 return _cl_UP(UPR, y);
44 return _cl_UP(UPR, x);
45 // Now xlen > 0, ylen > 0.
46 var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
48 var cl_GV_MI result = cl_GV_MI(xlen,R);
49 var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
51 copy_loop_up(xv->data,rv->data,ceiling(xlen,intDsize));
53 xor_loop_up(rv->data,yv->data,ceiling(ylen,intDsize));
54 return _cl_UP(UPR, result);
57 var cl_GV_MI result = cl_GV_MI(ylen,R);
58 var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
60 copy_loop_up(yv->data,rv->data,ceiling(ylen,intDsize));
62 xor_loop_up(rv->data,xv->data,ceiling(xlen,intDsize));
63 return _cl_UP(UPR, result);
65 // Now xlen = ylen > 0. Add and normalize simultaneously.
67 var uintL index = floor(xlen-1,intDsize);
68 var uintD rword = xv->data[index] ^ yv->data[index];
70 xlen = index*intDsize;
72 return _cl_UP(UPR, cl_null_GV_I);
74 xlen = index*intDsize;
75 integerlengthD(rword, xlen += );
77 var cl_GV_MI result = cl_GV_MI(xlen,R);
78 var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
79 copy_loop_up(xv->data,rv->data,index);
80 xor_loop_up(rv->data,yv->data,index);
81 rv->data[index] = rword;
82 return _cl_UP(UPR, result);
87 // In characteristic 2, x-y = x+y.
88 #define gf2_minus gf2_plus
90 // In characteristic 2, -x = x.
91 static const _cl_UP gf2_uminus (cl_heap_univpoly_ring* UPR, const _cl_UP& x)
97 #if !(defined(__sparc__) || defined(__sparc64__))
98 // Multiplication of polynomials over GF(2) can unfortunately not profit
99 // from hardware multiply instructions. Use a table instead.
100 // This is a 2^8 x 2^4 table. Maybe a 2^6 x 2^6 table would be better?
101 // (LiDIA uses a 2^8 x 2^8 table, which is way too large.)
102 static uint16 gf2_mul_table[0x100][0x10] =
104 { 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000,
105 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000, 0x000 },
106 { 0x000, 0x001, 0x002, 0x003, 0x004, 0x005, 0x006, 0x007,
107 0x008, 0x009, 0x00A, 0x00B, 0x00C, 0x00D, 0x00E, 0x00F },
108 { 0x000, 0x002, 0x004, 0x006, 0x008, 0x00A, 0x00C, 0x00E,
109 0x010, 0x012, 0x014, 0x016, 0x018, 0x01A, 0x01C, 0x01E },
110 { 0x000, 0x003, 0x006, 0x005, 0x00C, 0x00F, 0x00A, 0x009,
111 0x018, 0x01B, 0x01E, 0x01D, 0x014, 0x017, 0x012, 0x011 },
112 { 0x000, 0x004, 0x008, 0x00C, 0x010, 0x014, 0x018, 0x01C,
113 0x020, 0x024, 0x028, 0x02C, 0x030, 0x034, 0x038, 0x03C },
114 { 0x000, 0x005, 0x00A, 0x00F, 0x014, 0x011, 0x01E, 0x01B,
115 0x028, 0x02D, 0x022, 0x027, 0x03C, 0x039, 0x036, 0x033 },
116 { 0x000, 0x006, 0x00C, 0x00A, 0x018, 0x01E, 0x014, 0x012,
117 0x030, 0x036, 0x03C, 0x03A, 0x028, 0x02E, 0x024, 0x022 },
118 { 0x000, 0x007, 0x00E, 0x009, 0x01C, 0x01B, 0x012, 0x015,
119 0x038, 0x03F, 0x036, 0x031, 0x024, 0x023, 0x02A, 0x02D },
120 { 0x000, 0x008, 0x010, 0x018, 0x020, 0x028, 0x030, 0x038,
121 0x040, 0x048, 0x050, 0x058, 0x060, 0x068, 0x070, 0x078 },
122 { 0x000, 0x009, 0x012, 0x01B, 0x024, 0x02D, 0x036, 0x03F,
123 0x048, 0x041, 0x05A, 0x053, 0x06C, 0x065, 0x07E, 0x077 },
124 { 0x000, 0x00A, 0x014, 0x01E, 0x028, 0x022, 0x03C, 0x036,
125 0x050, 0x05A, 0x044, 0x04E, 0x078, 0x072, 0x06C, 0x066 },
126 { 0x000, 0x00B, 0x016, 0x01D, 0x02C, 0x027, 0x03A, 0x031,
127 0x058, 0x053, 0x04E, 0x045, 0x074, 0x07F, 0x062, 0x069 },
128 { 0x000, 0x00C, 0x018, 0x014, 0x030, 0x03C, 0x028, 0x024,
129 0x060, 0x06C, 0x078, 0x074, 0x050, 0x05C, 0x048, 0x044 },
130 { 0x000, 0x00D, 0x01A, 0x017, 0x034, 0x039, 0x02E, 0x023,
131 0x068, 0x065, 0x072, 0x07F, 0x05C, 0x051, 0x046, 0x04B },
132 { 0x000, 0x00E, 0x01C, 0x012, 0x038, 0x036, 0x024, 0x02A,
133 0x070, 0x07E, 0x06C, 0x062, 0x048, 0x046, 0x054, 0x05A },
134 { 0x000, 0x00F, 0x01E, 0x011, 0x03C, 0x033, 0x022, 0x02D,
135 0x078, 0x077, 0x066, 0x069, 0x044, 0x04B, 0x05A, 0x055 },
136 { 0x000, 0x010, 0x020, 0x030, 0x040, 0x050, 0x060, 0x070,
137 0x080, 0x090, 0x0A0, 0x0B0, 0x0C0, 0x0D0, 0x0E0, 0x0F0 },
138 { 0x000, 0x011, 0x022, 0x033, 0x044, 0x055, 0x066, 0x077,
139 0x088, 0x099, 0x0AA, 0x0BB, 0x0CC, 0x0DD, 0x0EE, 0x0FF },
140 { 0x000, 0x012, 0x024, 0x036, 0x048, 0x05A, 0x06C, 0x07E,
141 0x090, 0x082, 0x0B4, 0x0A6, 0x0D8, 0x0CA, 0x0FC, 0x0EE },
142 { 0x000, 0x013, 0x026, 0x035, 0x04C, 0x05F, 0x06A, 0x079,
143 0x098, 0x08B, 0x0BE, 0x0AD, 0x0D4, 0x0C7, 0x0F2, 0x0E1 },
144 { 0x000, 0x014, 0x028, 0x03C, 0x050, 0x044, 0x078, 0x06C,
145 0x0A0, 0x0B4, 0x088, 0x09C, 0x0F0, 0x0E4, 0x0D8, 0x0CC },
146 { 0x000, 0x015, 0x02A, 0x03F, 0x054, 0x041, 0x07E, 0x06B,
147 0x0A8, 0x0BD, 0x082, 0x097, 0x0FC, 0x0E9, 0x0D6, 0x0C3 },
148 { 0x000, 0x016, 0x02C, 0x03A, 0x058, 0x04E, 0x074, 0x062,
149 0x0B0, 0x0A6, 0x09C, 0x08A, 0x0E8, 0x0FE, 0x0C4, 0x0D2 },
150 { 0x000, 0x017, 0x02E, 0x039, 0x05C, 0x04B, 0x072, 0x065,
151 0x0B8, 0x0AF, 0x096, 0x081, 0x0E4, 0x0F3, 0x0CA, 0x0DD },
152 { 0x000, 0x018, 0x030, 0x028, 0x060, 0x078, 0x050, 0x048,
153 0x0C0, 0x0D8, 0x0F0, 0x0E8, 0x0A0, 0x0B8, 0x090, 0x088 },
154 { 0x000, 0x019, 0x032, 0x02B, 0x064, 0x07D, 0x056, 0x04F,
155 0x0C8, 0x0D1, 0x0FA, 0x0E3, 0x0AC, 0x0B5, 0x09E, 0x087 },
156 { 0x000, 0x01A, 0x034, 0x02E, 0x068, 0x072, 0x05C, 0x046,
157 0x0D0, 0x0CA, 0x0E4, 0x0FE, 0x0B8, 0x0A2, 0x08C, 0x096 },
158 { 0x000, 0x01B, 0x036, 0x02D, 0x06C, 0x077, 0x05A, 0x041,
159 0x0D8, 0x0C3, 0x0EE, 0x0F5, 0x0B4, 0x0AF, 0x082, 0x099 },
160 { 0x000, 0x01C, 0x038, 0x024, 0x070, 0x06C, 0x048, 0x054,
161 0x0E0, 0x0FC, 0x0D8, 0x0C4, 0x090, 0x08C, 0x0A8, 0x0B4 },
162 { 0x000, 0x01D, 0x03A, 0x027, 0x074, 0x069, 0x04E, 0x053,
163 0x0E8, 0x0F5, 0x0D2, 0x0CF, 0x09C, 0x081, 0x0A6, 0x0BB },
164 { 0x000, 0x01E, 0x03C, 0x022, 0x078, 0x066, 0x044, 0x05A,
165 0x0F0, 0x0EE, 0x0CC, 0x0D2, 0x088, 0x096, 0x0B4, 0x0AA },
166 { 0x000, 0x01F, 0x03E, 0x021, 0x07C, 0x063, 0x042, 0x05D,
167 0x0F8, 0x0E7, 0x0C6, 0x0D9, 0x084, 0x09B, 0x0BA, 0x0A5 },
168 { 0x000, 0x020, 0x040, 0x060, 0x080, 0x0A0, 0x0C0, 0x0E0,
169 0x100, 0x120, 0x140, 0x160, 0x180, 0x1A0, 0x1C0, 0x1E0 },
170 { 0x000, 0x021, 0x042, 0x063, 0x084, 0x0A5, 0x0C6, 0x0E7,
171 0x108, 0x129, 0x14A, 0x16B, 0x18C, 0x1AD, 0x1CE, 0x1EF },
172 { 0x000, 0x022, 0x044, 0x066, 0x088, 0x0AA, 0x0CC, 0x0EE,
173 0x110, 0x132, 0x154, 0x176, 0x198, 0x1BA, 0x1DC, 0x1FE },
174 { 0x000, 0x023, 0x046, 0x065, 0x08C, 0x0AF, 0x0CA, 0x0E9,
175 0x118, 0x13B, 0x15E, 0x17D, 0x194, 0x1B7, 0x1D2, 0x1F1 },
176 { 0x000, 0x024, 0x048, 0x06C, 0x090, 0x0B4, 0x0D8, 0x0FC,
177 0x120, 0x104, 0x168, 0x14C, 0x1B0, 0x194, 0x1F8, 0x1DC },
178 { 0x000, 0x025, 0x04A, 0x06F, 0x094, 0x0B1, 0x0DE, 0x0FB,
179 0x128, 0x10D, 0x162, 0x147, 0x1BC, 0x199, 0x1F6, 0x1D3 },
180 { 0x000, 0x026, 0x04C, 0x06A, 0x098, 0x0BE, 0x0D4, 0x0F2,
181 0x130, 0x116, 0x17C, 0x15A, 0x1A8, 0x18E, 0x1E4, 0x1C2 },
182 { 0x000, 0x027, 0x04E, 0x069, 0x09C, 0x0BB, 0x0D2, 0x0F5,
183 0x138, 0x11F, 0x176, 0x151, 0x1A4, 0x183, 0x1EA, 0x1CD },
184 { 0x000, 0x028, 0x050, 0x078, 0x0A0, 0x088, 0x0F0, 0x0D8,
185 0x140, 0x168, 0x110, 0x138, 0x1E0, 0x1C8, 0x1B0, 0x198 },
186 { 0x000, 0x029, 0x052, 0x07B, 0x0A4, 0x08D, 0x0F6, 0x0DF,
187 0x148, 0x161, 0x11A, 0x133, 0x1EC, 0x1C5, 0x1BE, 0x197 },
188 { 0x000, 0x02A, 0x054, 0x07E, 0x0A8, 0x082, 0x0FC, 0x0D6,
189 0x150, 0x17A, 0x104, 0x12E, 0x1F8, 0x1D2, 0x1AC, 0x186 },
190 { 0x000, 0x02B, 0x056, 0x07D, 0x0AC, 0x087, 0x0FA, 0x0D1,
191 0x158, 0x173, 0x10E, 0x125, 0x1F4, 0x1DF, 0x1A2, 0x189 },
192 { 0x000, 0x02C, 0x058, 0x074, 0x0B0, 0x09C, 0x0E8, 0x0C4,
193 0x160, 0x14C, 0x138, 0x114, 0x1D0, 0x1FC, 0x188, 0x1A4 },
194 { 0x000, 0x02D, 0x05A, 0x077, 0x0B4, 0x099, 0x0EE, 0x0C3,
195 0x168, 0x145, 0x132, 0x11F, 0x1DC, 0x1F1, 0x186, 0x1AB },
196 { 0x000, 0x02E, 0x05C, 0x072, 0x0B8, 0x096, 0x0E4, 0x0CA,
197 0x170, 0x15E, 0x12C, 0x102, 0x1C8, 0x1E6, 0x194, 0x1BA },
198 { 0x000, 0x02F, 0x05E, 0x071, 0x0BC, 0x093, 0x0E2, 0x0CD,
199 0x178, 0x157, 0x126, 0x109, 0x1C4, 0x1EB, 0x19A, 0x1B5 },
200 { 0x000, 0x030, 0x060, 0x050, 0x0C0, 0x0F0, 0x0A0, 0x090,
201 0x180, 0x1B0, 0x1E0, 0x1D0, 0x140, 0x170, 0x120, 0x110 },
202 { 0x000, 0x031, 0x062, 0x053, 0x0C4, 0x0F5, 0x0A6, 0x097,
203 0x188, 0x1B9, 0x1EA, 0x1DB, 0x14C, 0x17D, 0x12E, 0x11F },
204 { 0x000, 0x032, 0x064, 0x056, 0x0C8, 0x0FA, 0x0AC, 0x09E,
205 0x190, 0x1A2, 0x1F4, 0x1C6, 0x158, 0x16A, 0x13C, 0x10E },
206 { 0x000, 0x033, 0x066, 0x055, 0x0CC, 0x0FF, 0x0AA, 0x099,
207 0x198, 0x1AB, 0x1FE, 0x1CD, 0x154, 0x167, 0x132, 0x101 },
208 { 0x000, 0x034, 0x068, 0x05C, 0x0D0, 0x0E4, 0x0B8, 0x08C,
209 0x1A0, 0x194, 0x1C8, 0x1FC, 0x170, 0x144, 0x118, 0x12C },
210 { 0x000, 0x035, 0x06A, 0x05F, 0x0D4, 0x0E1, 0x0BE, 0x08B,
211 0x1A8, 0x19D, 0x1C2, 0x1F7, 0x17C, 0x149, 0x116, 0x123 },
212 { 0x000, 0x036, 0x06C, 0x05A, 0x0D8, 0x0EE, 0x0B4, 0x082,
213 0x1B0, 0x186, 0x1DC, 0x1EA, 0x168, 0x15E, 0x104, 0x132 },
214 { 0x000, 0x037, 0x06E, 0x059, 0x0DC, 0x0EB, 0x0B2, 0x085,
215 0x1B8, 0x18F, 0x1D6, 0x1E1, 0x164, 0x153, 0x10A, 0x13D },
216 { 0x000, 0x038, 0x070, 0x048, 0x0E0, 0x0D8, 0x090, 0x0A8,
217 0x1C0, 0x1F8, 0x1B0, 0x188, 0x120, 0x118, 0x150, 0x168 },
218 { 0x000, 0x039, 0x072, 0x04B, 0x0E4, 0x0DD, 0x096, 0x0AF,
219 0x1C8, 0x1F1, 0x1BA, 0x183, 0x12C, 0x115, 0x15E, 0x167 },
220 { 0x000, 0x03A, 0x074, 0x04E, 0x0E8, 0x0D2, 0x09C, 0x0A6,
221 0x1D0, 0x1EA, 0x1A4, 0x19E, 0x138, 0x102, 0x14C, 0x176 },
222 { 0x000, 0x03B, 0x076, 0x04D, 0x0EC, 0x0D7, 0x09A, 0x0A1,
223 0x1D8, 0x1E3, 0x1AE, 0x195, 0x134, 0x10F, 0x142, 0x179 },
224 { 0x000, 0x03C, 0x078, 0x044, 0x0F0, 0x0CC, 0x088, 0x0B4,
225 0x1E0, 0x1DC, 0x198, 0x1A4, 0x110, 0x12C, 0x168, 0x154 },
226 { 0x000, 0x03D, 0x07A, 0x047, 0x0F4, 0x0C9, 0x08E, 0x0B3,
227 0x1E8, 0x1D5, 0x192, 0x1AF, 0x11C, 0x121, 0x166, 0x15B },
228 { 0x000, 0x03E, 0x07C, 0x042, 0x0F8, 0x0C6, 0x084, 0x0BA,
229 0x1F0, 0x1CE, 0x18C, 0x1B2, 0x108, 0x136, 0x174, 0x14A },
230 { 0x000, 0x03F, 0x07E, 0x041, 0x0FC, 0x0C3, 0x082, 0x0BD,
231 0x1F8, 0x1C7, 0x186, 0x1B9, 0x104, 0x13B, 0x17A, 0x145 },
232 { 0x000, 0x040, 0x080, 0x0C0, 0x100, 0x140, 0x180, 0x1C0,
233 0x200, 0x240, 0x280, 0x2C0, 0x300, 0x340, 0x380, 0x3C0 },
234 { 0x000, 0x041, 0x082, 0x0C3, 0x104, 0x145, 0x186, 0x1C7,
235 0x208, 0x249, 0x28A, 0x2CB, 0x30C, 0x34D, 0x38E, 0x3CF },
236 { 0x000, 0x042, 0x084, 0x0C6, 0x108, 0x14A, 0x18C, 0x1CE,
237 0x210, 0x252, 0x294, 0x2D6, 0x318, 0x35A, 0x39C, 0x3DE },
238 { 0x000, 0x043, 0x086, 0x0C5, 0x10C, 0x14F, 0x18A, 0x1C9,
239 0x218, 0x25B, 0x29E, 0x2DD, 0x314, 0x357, 0x392, 0x3D1 },
240 { 0x000, 0x044, 0x088, 0x0CC, 0x110, 0x154, 0x198, 0x1DC,
241 0x220, 0x264, 0x2A8, 0x2EC, 0x330, 0x374, 0x3B8, 0x3FC },
242 { 0x000, 0x045, 0x08A, 0x0CF, 0x114, 0x151, 0x19E, 0x1DB,
243 0x228, 0x26D, 0x2A2, 0x2E7, 0x33C, 0x379, 0x3B6, 0x3F3 },
244 { 0x000, 0x046, 0x08C, 0x0CA, 0x118, 0x15E, 0x194, 0x1D2,
245 0x230, 0x276, 0x2BC, 0x2FA, 0x328, 0x36E, 0x3A4, 0x3E2 },
246 { 0x000, 0x047, 0x08E, 0x0C9, 0x11C, 0x15B, 0x192, 0x1D5,
247 0x238, 0x27F, 0x2B6, 0x2F1, 0x324, 0x363, 0x3AA, 0x3ED },
248 { 0x000, 0x048, 0x090, 0x0D8, 0x120, 0x168, 0x1B0, 0x1F8,
249 0x240, 0x208, 0x2D0, 0x298, 0x360, 0x328, 0x3F0, 0x3B8 },
250 { 0x000, 0x049, 0x092, 0x0DB, 0x124, 0x16D, 0x1B6, 0x1FF,
251 0x248, 0x201, 0x2DA, 0x293, 0x36C, 0x325, 0x3FE, 0x3B7 },
252 { 0x000, 0x04A, 0x094, 0x0DE, 0x128, 0x162, 0x1BC, 0x1F6,
253 0x250, 0x21A, 0x2C4, 0x28E, 0x378, 0x332, 0x3EC, 0x3A6 },
254 { 0x000, 0x04B, 0x096, 0x0DD, 0x12C, 0x167, 0x1BA, 0x1F1,
255 0x258, 0x213, 0x2CE, 0x285, 0x374, 0x33F, 0x3E2, 0x3A9 },
256 { 0x000, 0x04C, 0x098, 0x0D4, 0x130, 0x17C, 0x1A8, 0x1E4,
257 0x260, 0x22C, 0x2F8, 0x2B4, 0x350, 0x31C, 0x3C8, 0x384 },
258 { 0x000, 0x04D, 0x09A, 0x0D7, 0x134, 0x179, 0x1AE, 0x1E3,
259 0x268, 0x225, 0x2F2, 0x2BF, 0x35C, 0x311, 0x3C6, 0x38B },
260 { 0x000, 0x04E, 0x09C, 0x0D2, 0x138, 0x176, 0x1A4, 0x1EA,
261 0x270, 0x23E, 0x2EC, 0x2A2, 0x348, 0x306, 0x3D4, 0x39A },
262 { 0x000, 0x04F, 0x09E, 0x0D1, 0x13C, 0x173, 0x1A2, 0x1ED,
263 0x278, 0x237, 0x2E6, 0x2A9, 0x344, 0x30B, 0x3DA, 0x395 },
264 { 0x000, 0x050, 0x0A0, 0x0F0, 0x140, 0x110, 0x1E0, 0x1B0,
265 0x280, 0x2D0, 0x220, 0x270, 0x3C0, 0x390, 0x360, 0x330 },
266 { 0x000, 0x051, 0x0A2, 0x0F3, 0x144, 0x115, 0x1E6, 0x1B7,
267 0x288, 0x2D9, 0x22A, 0x27B, 0x3CC, 0x39D, 0x36E, 0x33F },
268 { 0x000, 0x052, 0x0A4, 0x0F6, 0x148, 0x11A, 0x1EC, 0x1BE,
269 0x290, 0x2C2, 0x234, 0x266, 0x3D8, 0x38A, 0x37C, 0x32E },
270 { 0x000, 0x053, 0x0A6, 0x0F5, 0x14C, 0x11F, 0x1EA, 0x1B9,
271 0x298, 0x2CB, 0x23E, 0x26D, 0x3D4, 0x387, 0x372, 0x321 },
272 { 0x000, 0x054, 0x0A8, 0x0FC, 0x150, 0x104, 0x1F8, 0x1AC,
273 0x2A0, 0x2F4, 0x208, 0x25C, 0x3F0, 0x3A4, 0x358, 0x30C },
274 { 0x000, 0x055, 0x0AA, 0x0FF, 0x154, 0x101, 0x1FE, 0x1AB,
275 0x2A8, 0x2FD, 0x202, 0x257, 0x3FC, 0x3A9, 0x356, 0x303 },
276 { 0x000, 0x056, 0x0AC, 0x0FA, 0x158, 0x10E, 0x1F4, 0x1A2,
277 0x2B0, 0x2E6, 0x21C, 0x24A, 0x3E8, 0x3BE, 0x344, 0x312 },
278 { 0x000, 0x057, 0x0AE, 0x0F9, 0x15C, 0x10B, 0x1F2, 0x1A5,
279 0x2B8, 0x2EF, 0x216, 0x241, 0x3E4, 0x3B3, 0x34A, 0x31D },
280 { 0x000, 0x058, 0x0B0, 0x0E8, 0x160, 0x138, 0x1D0, 0x188,
281 0x2C0, 0x298, 0x270, 0x228, 0x3A0, 0x3F8, 0x310, 0x348 },
282 { 0x000, 0x059, 0x0B2, 0x0EB, 0x164, 0x13D, 0x1D6, 0x18F,
283 0x2C8, 0x291, 0x27A, 0x223, 0x3AC, 0x3F5, 0x31E, 0x347 },
284 { 0x000, 0x05A, 0x0B4, 0x0EE, 0x168, 0x132, 0x1DC, 0x186,
285 0x2D0, 0x28A, 0x264, 0x23E, 0x3B8, 0x3E2, 0x30C, 0x356 },
286 { 0x000, 0x05B, 0x0B6, 0x0ED, 0x16C, 0x137, 0x1DA, 0x181,
287 0x2D8, 0x283, 0x26E, 0x235, 0x3B4, 0x3EF, 0x302, 0x359 },
288 { 0x000, 0x05C, 0x0B8, 0x0E4, 0x170, 0x12C, 0x1C8, 0x194,
289 0x2E0, 0x2BC, 0x258, 0x204, 0x390, 0x3CC, 0x328, 0x374 },
290 { 0x000, 0x05D, 0x0BA, 0x0E7, 0x174, 0x129, 0x1CE, 0x193,
291 0x2E8, 0x2B5, 0x252, 0x20F, 0x39C, 0x3C1, 0x326, 0x37B },
292 { 0x000, 0x05E, 0x0BC, 0x0E2, 0x178, 0x126, 0x1C4, 0x19A,
293 0x2F0, 0x2AE, 0x24C, 0x212, 0x388, 0x3D6, 0x334, 0x36A },
294 { 0x000, 0x05F, 0x0BE, 0x0E1, 0x17C, 0x123, 0x1C2, 0x19D,
295 0x2F8, 0x2A7, 0x246, 0x219, 0x384, 0x3DB, 0x33A, 0x365 },
296 { 0x000, 0x060, 0x0C0, 0x0A0, 0x180, 0x1E0, 0x140, 0x120,
297 0x300, 0x360, 0x3C0, 0x3A0, 0x280, 0x2E0, 0x240, 0x220 },
298 { 0x000, 0x061, 0x0C2, 0x0A3, 0x184, 0x1E5, 0x146, 0x127,
299 0x308, 0x369, 0x3CA, 0x3AB, 0x28C, 0x2ED, 0x24E, 0x22F },
300 { 0x000, 0x062, 0x0C4, 0x0A6, 0x188, 0x1EA, 0x14C, 0x12E,
301 0x310, 0x372, 0x3D4, 0x3B6, 0x298, 0x2FA, 0x25C, 0x23E },
302 { 0x000, 0x063, 0x0C6, 0x0A5, 0x18C, 0x1EF, 0x14A, 0x129,
303 0x318, 0x37B, 0x3DE, 0x3BD, 0x294, 0x2F7, 0x252, 0x231 },
304 { 0x000, 0x064, 0x0C8, 0x0AC, 0x190, 0x1F4, 0x158, 0x13C,
305 0x320, 0x344, 0x3E8, 0x38C, 0x2B0, 0x2D4, 0x278, 0x21C },
306 { 0x000, 0x065, 0x0CA, 0x0AF, 0x194, 0x1F1, 0x15E, 0x13B,
307 0x328, 0x34D, 0x3E2, 0x387, 0x2BC, 0x2D9, 0x276, 0x213 },
308 { 0x000, 0x066, 0x0CC, 0x0AA, 0x198, 0x1FE, 0x154, 0x132,
309 0x330, 0x356, 0x3FC, 0x39A, 0x2A8, 0x2CE, 0x264, 0x202 },
310 { 0x000, 0x067, 0x0CE, 0x0A9, 0x19C, 0x1FB, 0x152, 0x135,
311 0x338, 0x35F, 0x3F6, 0x391, 0x2A4, 0x2C3, 0x26A, 0x20D },
312 { 0x000, 0x068, 0x0D0, 0x0B8, 0x1A0, 0x1C8, 0x170, 0x118,
313 0x340, 0x328, 0x390, 0x3F8, 0x2E0, 0x288, 0x230, 0x258 },
314 { 0x000, 0x069, 0x0D2, 0x0BB, 0x1A4, 0x1CD, 0x176, 0x11F,
315 0x348, 0x321, 0x39A, 0x3F3, 0x2EC, 0x285, 0x23E, 0x257 },
316 { 0x000, 0x06A, 0x0D4, 0x0BE, 0x1A8, 0x1C2, 0x17C, 0x116,
317 0x350, 0x33A, 0x384, 0x3EE, 0x2F8, 0x292, 0x22C, 0x246 },
318 { 0x000, 0x06B, 0x0D6, 0x0BD, 0x1AC, 0x1C7, 0x17A, 0x111,
319 0x358, 0x333, 0x38E, 0x3E5, 0x2F4, 0x29F, 0x222, 0x249 },
320 { 0x000, 0x06C, 0x0D8, 0x0B4, 0x1B0, 0x1DC, 0x168, 0x104,
321 0x360, 0x30C, 0x3B8, 0x3D4, 0x2D0, 0x2BC, 0x208, 0x264 },
322 { 0x000, 0x06D, 0x0DA, 0x0B7, 0x1B4, 0x1D9, 0x16E, 0x103,
323 0x368, 0x305, 0x3B2, 0x3DF, 0x2DC, 0x2B1, 0x206, 0x26B },
324 { 0x000, 0x06E, 0x0DC, 0x0B2, 0x1B8, 0x1D6, 0x164, 0x10A,
325 0x370, 0x31E, 0x3AC, 0x3C2, 0x2C8, 0x2A6, 0x214, 0x27A },
326 { 0x000, 0x06F, 0x0DE, 0x0B1, 0x1BC, 0x1D3, 0x162, 0x10D,
327 0x378, 0x317, 0x3A6, 0x3C9, 0x2C4, 0x2AB, 0x21A, 0x275 },
328 { 0x000, 0x070, 0x0E0, 0x090, 0x1C0, 0x1B0, 0x120, 0x150,
329 0x380, 0x3F0, 0x360, 0x310, 0x240, 0x230, 0x2A0, 0x2D0 },
330 { 0x000, 0x071, 0x0E2, 0x093, 0x1C4, 0x1B5, 0x126, 0x157,
331 0x388, 0x3F9, 0x36A, 0x31B, 0x24C, 0x23D, 0x2AE, 0x2DF },
332 { 0x000, 0x072, 0x0E4, 0x096, 0x1C8, 0x1BA, 0x12C, 0x15E,
333 0x390, 0x3E2, 0x374, 0x306, 0x258, 0x22A, 0x2BC, 0x2CE },
334 { 0x000, 0x073, 0x0E6, 0x095, 0x1CC, 0x1BF, 0x12A, 0x159,
335 0x398, 0x3EB, 0x37E, 0x30D, 0x254, 0x227, 0x2B2, 0x2C1 },
336 { 0x000, 0x074, 0x0E8, 0x09C, 0x1D0, 0x1A4, 0x138, 0x14C,
337 0x3A0, 0x3D4, 0x348, 0x33C, 0x270, 0x204, 0x298, 0x2EC },
338 { 0x000, 0x075, 0x0EA, 0x09F, 0x1D4, 0x1A1, 0x13E, 0x14B,
339 0x3A8, 0x3DD, 0x342, 0x337, 0x27C, 0x209, 0x296, 0x2E3 },
340 { 0x000, 0x076, 0x0EC, 0x09A, 0x1D8, 0x1AE, 0x134, 0x142,
341 0x3B0, 0x3C6, 0x35C, 0x32A, 0x268, 0x21E, 0x284, 0x2F2 },
342 { 0x000, 0x077, 0x0EE, 0x099, 0x1DC, 0x1AB, 0x132, 0x145,
343 0x3B8, 0x3CF, 0x356, 0x321, 0x264, 0x213, 0x28A, 0x2FD },
344 { 0x000, 0x078, 0x0F0, 0x088, 0x1E0, 0x198, 0x110, 0x168,
345 0x3C0, 0x3B8, 0x330, 0x348, 0x220, 0x258, 0x2D0, 0x2A8 },
346 { 0x000, 0x079, 0x0F2, 0x08B, 0x1E4, 0x19D, 0x116, 0x16F,
347 0x3C8, 0x3B1, 0x33A, 0x343, 0x22C, 0x255, 0x2DE, 0x2A7 },
348 { 0x000, 0x07A, 0x0F4, 0x08E, 0x1E8, 0x192, 0x11C, 0x166,
349 0x3D0, 0x3AA, 0x324, 0x35E, 0x238, 0x242, 0x2CC, 0x2B6 },
350 { 0x000, 0x07B, 0x0F6, 0x08D, 0x1EC, 0x197, 0x11A, 0x161,
351 0x3D8, 0x3A3, 0x32E, 0x355, 0x234, 0x24F, 0x2C2, 0x2B9 },
352 { 0x000, 0x07C, 0x0F8, 0x084, 0x1F0, 0x18C, 0x108, 0x174,
353 0x3E0, 0x39C, 0x318, 0x364, 0x210, 0x26C, 0x2E8, 0x294 },
354 { 0x000, 0x07D, 0x0FA, 0x087, 0x1F4, 0x189, 0x10E, 0x173,
355 0x3E8, 0x395, 0x312, 0x36F, 0x21C, 0x261, 0x2E6, 0x29B },
356 { 0x000, 0x07E, 0x0FC, 0x082, 0x1F8, 0x186, 0x104, 0x17A,
357 0x3F0, 0x38E, 0x30C, 0x372, 0x208, 0x276, 0x2F4, 0x28A },
358 { 0x000, 0x07F, 0x0FE, 0x081, 0x1FC, 0x183, 0x102, 0x17D,
359 0x3F8, 0x387, 0x306, 0x379, 0x204, 0x27B, 0x2FA, 0x285 },
360 { 0x000, 0x080, 0x100, 0x180, 0x200, 0x280, 0x300, 0x380,
361 0x400, 0x480, 0x500, 0x580, 0x600, 0x680, 0x700, 0x780 },
362 { 0x000, 0x081, 0x102, 0x183, 0x204, 0x285, 0x306, 0x387,
363 0x408, 0x489, 0x50A, 0x58B, 0x60C, 0x68D, 0x70E, 0x78F },
364 { 0x000, 0x082, 0x104, 0x186, 0x208, 0x28A, 0x30C, 0x38E,
365 0x410, 0x492, 0x514, 0x596, 0x618, 0x69A, 0x71C, 0x79E },
366 { 0x000, 0x083, 0x106, 0x185, 0x20C, 0x28F, 0x30A, 0x389,
367 0x418, 0x49B, 0x51E, 0x59D, 0x614, 0x697, 0x712, 0x791 },
368 { 0x000, 0x084, 0x108, 0x18C, 0x210, 0x294, 0x318, 0x39C,
369 0x420, 0x4A4, 0x528, 0x5AC, 0x630, 0x6B4, 0x738, 0x7BC },
370 { 0x000, 0x085, 0x10A, 0x18F, 0x214, 0x291, 0x31E, 0x39B,
371 0x428, 0x4AD, 0x522, 0x5A7, 0x63C, 0x6B9, 0x736, 0x7B3 },
372 { 0x000, 0x086, 0x10C, 0x18A, 0x218, 0x29E, 0x314, 0x392,
373 0x430, 0x4B6, 0x53C, 0x5BA, 0x628, 0x6AE, 0x724, 0x7A2 },
374 { 0x000, 0x087, 0x10E, 0x189, 0x21C, 0x29B, 0x312, 0x395,
375 0x438, 0x4BF, 0x536, 0x5B1, 0x624, 0x6A3, 0x72A, 0x7AD },
376 { 0x000, 0x088, 0x110, 0x198, 0x220, 0x2A8, 0x330, 0x3B8,
377 0x440, 0x4C8, 0x550, 0x5D8, 0x660, 0x6E8, 0x770, 0x7F8 },
378 { 0x000, 0x089, 0x112, 0x19B, 0x224, 0x2AD, 0x336, 0x3BF,
379 0x448, 0x4C1, 0x55A, 0x5D3, 0x66C, 0x6E5, 0x77E, 0x7F7 },
380 { 0x000, 0x08A, 0x114, 0x19E, 0x228, 0x2A2, 0x33C, 0x3B6,
381 0x450, 0x4DA, 0x544, 0x5CE, 0x678, 0x6F2, 0x76C, 0x7E6 },
382 { 0x000, 0x08B, 0x116, 0x19D, 0x22C, 0x2A7, 0x33A, 0x3B1,
383 0x458, 0x4D3, 0x54E, 0x5C5, 0x674, 0x6FF, 0x762, 0x7E9 },
384 { 0x000, 0x08C, 0x118, 0x194, 0x230, 0x2BC, 0x328, 0x3A4,
385 0x460, 0x4EC, 0x578, 0x5F4, 0x650, 0x6DC, 0x748, 0x7C4 },
386 { 0x000, 0x08D, 0x11A, 0x197, 0x234, 0x2B9, 0x32E, 0x3A3,
387 0x468, 0x4E5, 0x572, 0x5FF, 0x65C, 0x6D1, 0x746, 0x7CB },
388 { 0x000, 0x08E, 0x11C, 0x192, 0x238, 0x2B6, 0x324, 0x3AA,
389 0x470, 0x4FE, 0x56C, 0x5E2, 0x648, 0x6C6, 0x754, 0x7DA },
390 { 0x000, 0x08F, 0x11E, 0x191, 0x23C, 0x2B3, 0x322, 0x3AD,
391 0x478, 0x4F7, 0x566, 0x5E9, 0x644, 0x6CB, 0x75A, 0x7D5 },
392 { 0x000, 0x090, 0x120, 0x1B0, 0x240, 0x2D0, 0x360, 0x3F0,
393 0x480, 0x410, 0x5A0, 0x530, 0x6C0, 0x650, 0x7E0, 0x770 },
394 { 0x000, 0x091, 0x122, 0x1B3, 0x244, 0x2D5, 0x366, 0x3F7,
395 0x488, 0x419, 0x5AA, 0x53B, 0x6CC, 0x65D, 0x7EE, 0x77F },
396 { 0x000, 0x092, 0x124, 0x1B6, 0x248, 0x2DA, 0x36C, 0x3FE,
397 0x490, 0x402, 0x5B4, 0x526, 0x6D8, 0x64A, 0x7FC, 0x76E },
398 { 0x000, 0x093, 0x126, 0x1B5, 0x24C, 0x2DF, 0x36A, 0x3F9,
399 0x498, 0x40B, 0x5BE, 0x52D, 0x6D4, 0x647, 0x7F2, 0x761 },
400 { 0x000, 0x094, 0x128, 0x1BC, 0x250, 0x2C4, 0x378, 0x3EC,
401 0x4A0, 0x434, 0x588, 0x51C, 0x6F0, 0x664, 0x7D8, 0x74C },
402 { 0x000, 0x095, 0x12A, 0x1BF, 0x254, 0x2C1, 0x37E, 0x3EB,
403 0x4A8, 0x43D, 0x582, 0x517, 0x6FC, 0x669, 0x7D6, 0x743 },
404 { 0x000, 0x096, 0x12C, 0x1BA, 0x258, 0x2CE, 0x374, 0x3E2,
405 0x4B0, 0x426, 0x59C, 0x50A, 0x6E8, 0x67E, 0x7C4, 0x752 },
406 { 0x000, 0x097, 0x12E, 0x1B9, 0x25C, 0x2CB, 0x372, 0x3E5,
407 0x4B8, 0x42F, 0x596, 0x501, 0x6E4, 0x673, 0x7CA, 0x75D },
408 { 0x000, 0x098, 0x130, 0x1A8, 0x260, 0x2F8, 0x350, 0x3C8,
409 0x4C0, 0x458, 0x5F0, 0x568, 0x6A0, 0x638, 0x790, 0x708 },
410 { 0x000, 0x099, 0x132, 0x1AB, 0x264, 0x2FD, 0x356, 0x3CF,
411 0x4C8, 0x451, 0x5FA, 0x563, 0x6AC, 0x635, 0x79E, 0x707 },
412 { 0x000, 0x09A, 0x134, 0x1AE, 0x268, 0x2F2, 0x35C, 0x3C6,
413 0x4D0, 0x44A, 0x5E4, 0x57E, 0x6B8, 0x622, 0x78C, 0x716 },
414 { 0x000, 0x09B, 0x136, 0x1AD, 0x26C, 0x2F7, 0x35A, 0x3C1,
415 0x4D8, 0x443, 0x5EE, 0x575, 0x6B4, 0x62F, 0x782, 0x719 },
416 { 0x000, 0x09C, 0x138, 0x1A4, 0x270, 0x2EC, 0x348, 0x3D4,
417 0x4E0, 0x47C, 0x5D8, 0x544, 0x690, 0x60C, 0x7A8, 0x734 },
418 { 0x000, 0x09D, 0x13A, 0x1A7, 0x274, 0x2E9, 0x34E, 0x3D3,
419 0x4E8, 0x475, 0x5D2, 0x54F, 0x69C, 0x601, 0x7A6, 0x73B },
420 { 0x000, 0x09E, 0x13C, 0x1A2, 0x278, 0x2E6, 0x344, 0x3DA,
421 0x4F0, 0x46E, 0x5CC, 0x552, 0x688, 0x616, 0x7B4, 0x72A },
422 { 0x000, 0x09F, 0x13E, 0x1A1, 0x27C, 0x2E3, 0x342, 0x3DD,
423 0x4F8, 0x467, 0x5C6, 0x559, 0x684, 0x61B, 0x7BA, 0x725 },
424 { 0x000, 0x0A0, 0x140, 0x1E0, 0x280, 0x220, 0x3C0, 0x360,
425 0x500, 0x5A0, 0x440, 0x4E0, 0x780, 0x720, 0x6C0, 0x660 },
426 { 0x000, 0x0A1, 0x142, 0x1E3, 0x284, 0x225, 0x3C6, 0x367,
427 0x508, 0x5A9, 0x44A, 0x4EB, 0x78C, 0x72D, 0x6CE, 0x66F },
428 { 0x000, 0x0A2, 0x144, 0x1E6, 0x288, 0x22A, 0x3CC, 0x36E,
429 0x510, 0x5B2, 0x454, 0x4F6, 0x798, 0x73A, 0x6DC, 0x67E },
430 { 0x000, 0x0A3, 0x146, 0x1E5, 0x28C, 0x22F, 0x3CA, 0x369,
431 0x518, 0x5BB, 0x45E, 0x4FD, 0x794, 0x737, 0x6D2, 0x671 },
432 { 0x000, 0x0A4, 0x148, 0x1EC, 0x290, 0x234, 0x3D8, 0x37C,
433 0x520, 0x584, 0x468, 0x4CC, 0x7B0, 0x714, 0x6F8, 0x65C },
434 { 0x000, 0x0A5, 0x14A, 0x1EF, 0x294, 0x231, 0x3DE, 0x37B,
435 0x528, 0x58D, 0x462, 0x4C7, 0x7BC, 0x719, 0x6F6, 0x653 },
436 { 0x000, 0x0A6, 0x14C, 0x1EA, 0x298, 0x23E, 0x3D4, 0x372,
437 0x530, 0x596, 0x47C, 0x4DA, 0x7A8, 0x70E, 0x6E4, 0x642 },
438 { 0x000, 0x0A7, 0x14E, 0x1E9, 0x29C, 0x23B, 0x3D2, 0x375,
439 0x538, 0x59F, 0x476, 0x4D1, 0x7A4, 0x703, 0x6EA, 0x64D },
440 { 0x000, 0x0A8, 0x150, 0x1F8, 0x2A0, 0x208, 0x3F0, 0x358,
441 0x540, 0x5E8, 0x410, 0x4B8, 0x7E0, 0x748, 0x6B0, 0x618 },
442 { 0x000, 0x0A9, 0x152, 0x1FB, 0x2A4, 0x20D, 0x3F6, 0x35F,
443 0x548, 0x5E1, 0x41A, 0x4B3, 0x7EC, 0x745, 0x6BE, 0x617 },
444 { 0x000, 0x0AA, 0x154, 0x1FE, 0x2A8, 0x202, 0x3FC, 0x356,
445 0x550, 0x5FA, 0x404, 0x4AE, 0x7F8, 0x752, 0x6AC, 0x606 },
446 { 0x000, 0x0AB, 0x156, 0x1FD, 0x2AC, 0x207, 0x3FA, 0x351,
447 0x558, 0x5F3, 0x40E, 0x4A5, 0x7F4, 0x75F, 0x6A2, 0x609 },
448 { 0x000, 0x0AC, 0x158, 0x1F4, 0x2B0, 0x21C, 0x3E8, 0x344,
449 0x560, 0x5CC, 0x438, 0x494, 0x7D0, 0x77C, 0x688, 0x624 },
450 { 0x000, 0x0AD, 0x15A, 0x1F7, 0x2B4, 0x219, 0x3EE, 0x343,
451 0x568, 0x5C5, 0x432, 0x49F, 0x7DC, 0x771, 0x686, 0x62B },
452 { 0x000, 0x0AE, 0x15C, 0x1F2, 0x2B8, 0x216, 0x3E4, 0x34A,
453 0x570, 0x5DE, 0x42C, 0x482, 0x7C8, 0x766, 0x694, 0x63A },
454 { 0x000, 0x0AF, 0x15E, 0x1F1, 0x2BC, 0x213, 0x3E2, 0x34D,
455 0x578, 0x5D7, 0x426, 0x489, 0x7C4, 0x76B, 0x69A, 0x635 },
456 { 0x000, 0x0B0, 0x160, 0x1D0, 0x2C0, 0x270, 0x3A0, 0x310,
457 0x580, 0x530, 0x4E0, 0x450, 0x740, 0x7F0, 0x620, 0x690 },
458 { 0x000, 0x0B1, 0x162, 0x1D3, 0x2C4, 0x275, 0x3A6, 0x317,
459 0x588, 0x539, 0x4EA, 0x45B, 0x74C, 0x7FD, 0x62E, 0x69F },
460 { 0x000, 0x0B2, 0x164, 0x1D6, 0x2C8, 0x27A, 0x3AC, 0x31E,
461 0x590, 0x522, 0x4F4, 0x446, 0x758, 0x7EA, 0x63C, 0x68E },
462 { 0x000, 0x0B3, 0x166, 0x1D5, 0x2CC, 0x27F, 0x3AA, 0x319,
463 0x598, 0x52B, 0x4FE, 0x44D, 0x754, 0x7E7, 0x632, 0x681 },
464 { 0x000, 0x0B4, 0x168, 0x1DC, 0x2D0, 0x264, 0x3B8, 0x30C,
465 0x5A0, 0x514, 0x4C8, 0x47C, 0x770, 0x7C4, 0x618, 0x6AC },
466 { 0x000, 0x0B5, 0x16A, 0x1DF, 0x2D4, 0x261, 0x3BE, 0x30B,
467 0x5A8, 0x51D, 0x4C2, 0x477, 0x77C, 0x7C9, 0x616, 0x6A3 },
468 { 0x000, 0x0B6, 0x16C, 0x1DA, 0x2D8, 0x26E, 0x3B4, 0x302,
469 0x5B0, 0x506, 0x4DC, 0x46A, 0x768, 0x7DE, 0x604, 0x6B2 },
470 { 0x000, 0x0B7, 0x16E, 0x1D9, 0x2DC, 0x26B, 0x3B2, 0x305,
471 0x5B8, 0x50F, 0x4D6, 0x461, 0x764, 0x7D3, 0x60A, 0x6BD },
472 { 0x000, 0x0B8, 0x170, 0x1C8, 0x2E0, 0x258, 0x390, 0x328,
473 0x5C0, 0x578, 0x4B0, 0x408, 0x720, 0x798, 0x650, 0x6E8 },
474 { 0x000, 0x0B9, 0x172, 0x1CB, 0x2E4, 0x25D, 0x396, 0x32F,
475 0x5C8, 0x571, 0x4BA, 0x403, 0x72C, 0x795, 0x65E, 0x6E7 },
476 { 0x000, 0x0BA, 0x174, 0x1CE, 0x2E8, 0x252, 0x39C, 0x326,
477 0x5D0, 0x56A, 0x4A4, 0x41E, 0x738, 0x782, 0x64C, 0x6F6 },
478 { 0x000, 0x0BB, 0x176, 0x1CD, 0x2EC, 0x257, 0x39A, 0x321,
479 0x5D8, 0x563, 0x4AE, 0x415, 0x734, 0x78F, 0x642, 0x6F9 },
480 { 0x000, 0x0BC, 0x178, 0x1C4, 0x2F0, 0x24C, 0x388, 0x334,
481 0x5E0, 0x55C, 0x498, 0x424, 0x710, 0x7AC, 0x668, 0x6D4 },
482 { 0x000, 0x0BD, 0x17A, 0x1C7, 0x2F4, 0x249, 0x38E, 0x333,
483 0x5E8, 0x555, 0x492, 0x42F, 0x71C, 0x7A1, 0x666, 0x6DB },
484 { 0x000, 0x0BE, 0x17C, 0x1C2, 0x2F8, 0x246, 0x384, 0x33A,
485 0x5F0, 0x54E, 0x48C, 0x432, 0x708, 0x7B6, 0x674, 0x6CA },
486 { 0x000, 0x0BF, 0x17E, 0x1C1, 0x2FC, 0x243, 0x382, 0x33D,
487 0x5F8, 0x547, 0x486, 0x439, 0x704, 0x7BB, 0x67A, 0x6C5 },
488 { 0x000, 0x0C0, 0x180, 0x140, 0x300, 0x3C0, 0x280, 0x240,
489 0x600, 0x6C0, 0x780, 0x740, 0x500, 0x5C0, 0x480, 0x440 },
490 { 0x000, 0x0C1, 0x182, 0x143, 0x304, 0x3C5, 0x286, 0x247,
491 0x608, 0x6C9, 0x78A, 0x74B, 0x50C, 0x5CD, 0x48E, 0x44F },
492 { 0x000, 0x0C2, 0x184, 0x146, 0x308, 0x3CA, 0x28C, 0x24E,
493 0x610, 0x6D2, 0x794, 0x756, 0x518, 0x5DA, 0x49C, 0x45E },
494 { 0x000, 0x0C3, 0x186, 0x145, 0x30C, 0x3CF, 0x28A, 0x249,
495 0x618, 0x6DB, 0x79E, 0x75D, 0x514, 0x5D7, 0x492, 0x451 },
496 { 0x000, 0x0C4, 0x188, 0x14C, 0x310, 0x3D4, 0x298, 0x25C,
497 0x620, 0x6E4, 0x7A8, 0x76C, 0x530, 0x5F4, 0x4B8, 0x47C },
498 { 0x000, 0x0C5, 0x18A, 0x14F, 0x314, 0x3D1, 0x29E, 0x25B,
499 0x628, 0x6ED, 0x7A2, 0x767, 0x53C, 0x5F9, 0x4B6, 0x473 },
500 { 0x000, 0x0C6, 0x18C, 0x14A, 0x318, 0x3DE, 0x294, 0x252,
501 0x630, 0x6F6, 0x7BC, 0x77A, 0x528, 0x5EE, 0x4A4, 0x462 },
502 { 0x000, 0x0C7, 0x18E, 0x149, 0x31C, 0x3DB, 0x292, 0x255,
503 0x638, 0x6FF, 0x7B6, 0x771, 0x524, 0x5E3, 0x4AA, 0x46D },
504 { 0x000, 0x0C8, 0x190, 0x158, 0x320, 0x3E8, 0x2B0, 0x278,
505 0x640, 0x688, 0x7D0, 0x718, 0x560, 0x5A8, 0x4F0, 0x438 },
506 { 0x000, 0x0C9, 0x192, 0x15B, 0x324, 0x3ED, 0x2B6, 0x27F,
507 0x648, 0x681, 0x7DA, 0x713, 0x56C, 0x5A5, 0x4FE, 0x437 },
508 { 0x000, 0x0CA, 0x194, 0x15E, 0x328, 0x3E2, 0x2BC, 0x276,
509 0x650, 0x69A, 0x7C4, 0x70E, 0x578, 0x5B2, 0x4EC, 0x426 },
510 { 0x000, 0x0CB, 0x196, 0x15D, 0x32C, 0x3E7, 0x2BA, 0x271,
511 0x658, 0x693, 0x7CE, 0x705, 0x574, 0x5BF, 0x4E2, 0x429 },
512 { 0x000, 0x0CC, 0x198, 0x154, 0x330, 0x3FC, 0x2A8, 0x264,
513 0x660, 0x6AC, 0x7F8, 0x734, 0x550, 0x59C, 0x4C8, 0x404 },
514 { 0x000, 0x0CD, 0x19A, 0x157, 0x334, 0x3F9, 0x2AE, 0x263,
515 0x668, 0x6A5, 0x7F2, 0x73F, 0x55C, 0x591, 0x4C6, 0x40B },
516 { 0x000, 0x0CE, 0x19C, 0x152, 0x338, 0x3F6, 0x2A4, 0x26A,
517 0x670, 0x6BE, 0x7EC, 0x722, 0x548, 0x586, 0x4D4, 0x41A },
518 { 0x000, 0x0CF, 0x19E, 0x151, 0x33C, 0x3F3, 0x2A2, 0x26D,
519 0x678, 0x6B7, 0x7E6, 0x729, 0x544, 0x58B, 0x4DA, 0x415 },
520 { 0x000, 0x0D0, 0x1A0, 0x170, 0x340, 0x390, 0x2E0, 0x230,
521 0x680, 0x650, 0x720, 0x7F0, 0x5C0, 0x510, 0x460, 0x4B0 },
522 { 0x000, 0x0D1, 0x1A2, 0x173, 0x344, 0x395, 0x2E6, 0x237,
523 0x688, 0x659, 0x72A, 0x7FB, 0x5CC, 0x51D, 0x46E, 0x4BF },
524 { 0x000, 0x0D2, 0x1A4, 0x176, 0x348, 0x39A, 0x2EC, 0x23E,
525 0x690, 0x642, 0x734, 0x7E6, 0x5D8, 0x50A, 0x47C, 0x4AE },
526 { 0x000, 0x0D3, 0x1A6, 0x175, 0x34C, 0x39F, 0x2EA, 0x239,
527 0x698, 0x64B, 0x73E, 0x7ED, 0x5D4, 0x507, 0x472, 0x4A1 },
528 { 0x000, 0x0D4, 0x1A8, 0x17C, 0x350, 0x384, 0x2F8, 0x22C,
529 0x6A0, 0x674, 0x708, 0x7DC, 0x5F0, 0x524, 0x458, 0x48C },
530 { 0x000, 0x0D5, 0x1AA, 0x17F, 0x354, 0x381, 0x2FE, 0x22B,
531 0x6A8, 0x67D, 0x702, 0x7D7, 0x5FC, 0x529, 0x456, 0x483 },
532 { 0x000, 0x0D6, 0x1AC, 0x17A, 0x358, 0x38E, 0x2F4, 0x222,
533 0x6B0, 0x666, 0x71C, 0x7CA, 0x5E8, 0x53E, 0x444, 0x492 },
534 { 0x000, 0x0D7, 0x1AE, 0x179, 0x35C, 0x38B, 0x2F2, 0x225,
535 0x6B8, 0x66F, 0x716, 0x7C1, 0x5E4, 0x533, 0x44A, 0x49D },
536 { 0x000, 0x0D8, 0x1B0, 0x168, 0x360, 0x3B8, 0x2D0, 0x208,
537 0x6C0, 0x618, 0x770, 0x7A8, 0x5A0, 0x578, 0x410, 0x4C8 },
538 { 0x000, 0x0D9, 0x1B2, 0x16B, 0x364, 0x3BD, 0x2D6, 0x20F,
539 0x6C8, 0x611, 0x77A, 0x7A3, 0x5AC, 0x575, 0x41E, 0x4C7 },
540 { 0x000, 0x0DA, 0x1B4, 0x16E, 0x368, 0x3B2, 0x2DC, 0x206,
541 0x6D0, 0x60A, 0x764, 0x7BE, 0x5B8, 0x562, 0x40C, 0x4D6 },
542 { 0x000, 0x0DB, 0x1B6, 0x16D, 0x36C, 0x3B7, 0x2DA, 0x201,
543 0x6D8, 0x603, 0x76E, 0x7B5, 0x5B4, 0x56F, 0x402, 0x4D9 },
544 { 0x000, 0x0DC, 0x1B8, 0x164, 0x370, 0x3AC, 0x2C8, 0x214,
545 0x6E0, 0x63C, 0x758, 0x784, 0x590, 0x54C, 0x428, 0x4F4 },
546 { 0x000, 0x0DD, 0x1BA, 0x167, 0x374, 0x3A9, 0x2CE, 0x213,
547 0x6E8, 0x635, 0x752, 0x78F, 0x59C, 0x541, 0x426, 0x4FB },
548 { 0x000, 0x0DE, 0x1BC, 0x162, 0x378, 0x3A6, 0x2C4, 0x21A,
549 0x6F0, 0x62E, 0x74C, 0x792, 0x588, 0x556, 0x434, 0x4EA },
550 { 0x000, 0x0DF, 0x1BE, 0x161, 0x37C, 0x3A3, 0x2C2, 0x21D,
551 0x6F8, 0x627, 0x746, 0x799, 0x584, 0x55B, 0x43A, 0x4E5 },
552 { 0x000, 0x0E0, 0x1C0, 0x120, 0x380, 0x360, 0x240, 0x2A0,
553 0x700, 0x7E0, 0x6C0, 0x620, 0x480, 0x460, 0x540, 0x5A0 },
554 { 0x000, 0x0E1, 0x1C2, 0x123, 0x384, 0x365, 0x246, 0x2A7,
555 0x708, 0x7E9, 0x6CA, 0x62B, 0x48C, 0x46D, 0x54E, 0x5AF },
556 { 0x000, 0x0E2, 0x1C4, 0x126, 0x388, 0x36A, 0x24C, 0x2AE,
557 0x710, 0x7F2, 0x6D4, 0x636, 0x498, 0x47A, 0x55C, 0x5BE },
558 { 0x000, 0x0E3, 0x1C6, 0x125, 0x38C, 0x36F, 0x24A, 0x2A9,
559 0x718, 0x7FB, 0x6DE, 0x63D, 0x494, 0x477, 0x552, 0x5B1 },
560 { 0x000, 0x0E4, 0x1C8, 0x12C, 0x390, 0x374, 0x258, 0x2BC,
561 0x720, 0x7C4, 0x6E8, 0x60C, 0x4B0, 0x454, 0x578, 0x59C },
562 { 0x000, 0x0E5, 0x1CA, 0x12F, 0x394, 0x371, 0x25E, 0x2BB,
563 0x728, 0x7CD, 0x6E2, 0x607, 0x4BC, 0x459, 0x576, 0x593 },
564 { 0x000, 0x0E6, 0x1CC, 0x12A, 0x398, 0x37E, 0x254, 0x2B2,
565 0x730, 0x7D6, 0x6FC, 0x61A, 0x4A8, 0x44E, 0x564, 0x582 },
566 { 0x000, 0x0E7, 0x1CE, 0x129, 0x39C, 0x37B, 0x252, 0x2B5,
567 0x738, 0x7DF, 0x6F6, 0x611, 0x4A4, 0x443, 0x56A, 0x58D },
568 { 0x000, 0x0E8, 0x1D0, 0x138, 0x3A0, 0x348, 0x270, 0x298,
569 0x740, 0x7A8, 0x690, 0x678, 0x4E0, 0x408, 0x530, 0x5D8 },
570 { 0x000, 0x0E9, 0x1D2, 0x13B, 0x3A4, 0x34D, 0x276, 0x29F,
571 0x748, 0x7A1, 0x69A, 0x673, 0x4EC, 0x405, 0x53E, 0x5D7 },
572 { 0x000, 0x0EA, 0x1D4, 0x13E, 0x3A8, 0x342, 0x27C, 0x296,
573 0x750, 0x7BA, 0x684, 0x66E, 0x4F8, 0x412, 0x52C, 0x5C6 },
574 { 0x000, 0x0EB, 0x1D6, 0x13D, 0x3AC, 0x347, 0x27A, 0x291,
575 0x758, 0x7B3, 0x68E, 0x665, 0x4F4, 0x41F, 0x522, 0x5C9 },
576 { 0x000, 0x0EC, 0x1D8, 0x134, 0x3B0, 0x35C, 0x268, 0x284,
577 0x760, 0x78C, 0x6B8, 0x654, 0x4D0, 0x43C, 0x508, 0x5E4 },
578 { 0x000, 0x0ED, 0x1DA, 0x137, 0x3B4, 0x359, 0x26E, 0x283,
579 0x768, 0x785, 0x6B2, 0x65F, 0x4DC, 0x431, 0x506, 0x5EB },
580 { 0x000, 0x0EE, 0x1DC, 0x132, 0x3B8, 0x356, 0x264, 0x28A,
581 0x770, 0x79E, 0x6AC, 0x642, 0x4C8, 0x426, 0x514, 0x5FA },
582 { 0x000, 0x0EF, 0x1DE, 0x131, 0x3BC, 0x353, 0x262, 0x28D,
583 0x778, 0x797, 0x6A6, 0x649, 0x4C4, 0x42B, 0x51A, 0x5F5 },
584 { 0x000, 0x0F0, 0x1E0, 0x110, 0x3C0, 0x330, 0x220, 0x2D0,
585 0x780, 0x770, 0x660, 0x690, 0x440, 0x4B0, 0x5A0, 0x550 },
586 { 0x000, 0x0F1, 0x1E2, 0x113, 0x3C4, 0x335, 0x226, 0x2D7,
587 0x788, 0x779, 0x66A, 0x69B, 0x44C, 0x4BD, 0x5AE, 0x55F },
588 { 0x000, 0x0F2, 0x1E4, 0x116, 0x3C8, 0x33A, 0x22C, 0x2DE,
589 0x790, 0x762, 0x674, 0x686, 0x458, 0x4AA, 0x5BC, 0x54E },
590 { 0x000, 0x0F3, 0x1E6, 0x115, 0x3CC, 0x33F, 0x22A, 0x2D9,
591 0x798, 0x76B, 0x67E, 0x68D, 0x454, 0x4A7, 0x5B2, 0x541 },
592 { 0x000, 0x0F4, 0x1E8, 0x11C, 0x3D0, 0x324, 0x238, 0x2CC,
593 0x7A0, 0x754, 0x648, 0x6BC, 0x470, 0x484, 0x598, 0x56C },
594 { 0x000, 0x0F5, 0x1EA, 0x11F, 0x3D4, 0x321, 0x23E, 0x2CB,
595 0x7A8, 0x75D, 0x642, 0x6B7, 0x47C, 0x489, 0x596, 0x563 },
596 { 0x000, 0x0F6, 0x1EC, 0x11A, 0x3D8, 0x32E, 0x234, 0x2C2,
597 0x7B0, 0x746, 0x65C, 0x6AA, 0x468, 0x49E, 0x584, 0x572 },
598 { 0x000, 0x0F7, 0x1EE, 0x119, 0x3DC, 0x32B, 0x232, 0x2C5,
599 0x7B8, 0x74F, 0x656, 0x6A1, 0x464, 0x493, 0x58A, 0x57D },
600 { 0x000, 0x0F8, 0x1F0, 0x108, 0x3E0, 0x318, 0x210, 0x2E8,
601 0x7C0, 0x738, 0x630, 0x6C8, 0x420, 0x4D8, 0x5D0, 0x528 },
602 { 0x000, 0x0F9, 0x1F2, 0x10B, 0x3E4, 0x31D, 0x216, 0x2EF,
603 0x7C8, 0x731, 0x63A, 0x6C3, 0x42C, 0x4D5, 0x5DE, 0x527 },
604 { 0x000, 0x0FA, 0x1F4, 0x10E, 0x3E8, 0x312, 0x21C, 0x2E6,
605 0x7D0, 0x72A, 0x624, 0x6DE, 0x438, 0x4C2, 0x5CC, 0x536 },
606 { 0x000, 0x0FB, 0x1F6, 0x10D, 0x3EC, 0x317, 0x21A, 0x2E1,
607 0x7D8, 0x723, 0x62E, 0x6D5, 0x434, 0x4CF, 0x5C2, 0x539 },
608 { 0x000, 0x0FC, 0x1F8, 0x104, 0x3F0, 0x30C, 0x208, 0x2F4,
609 0x7E0, 0x71C, 0x618, 0x6E4, 0x410, 0x4EC, 0x5E8, 0x514 },
610 { 0x000, 0x0FD, 0x1FA, 0x107, 0x3F4, 0x309, 0x20E, 0x2F3,
611 0x7E8, 0x715, 0x612, 0x6EF, 0x41C, 0x4E1, 0x5E6, 0x51B },
612 { 0x000, 0x0FE, 0x1FC, 0x102, 0x3F8, 0x306, 0x204, 0x2FA,
613 0x7F0, 0x70E, 0x60C, 0x6F2, 0x408, 0x4F6, 0x5F4, 0x50A },
614 { 0x000, 0x0FF, 0x1FE, 0x101, 0x3FC, 0x303, 0x202, 0x2FD,
615 0x7F8, 0x707, 0x606, 0x6F9, 0x404, 0x4FB, 0x5FA, 0x505 }
617 // Generated in CLISP:
621 // (dotimes (b 4) (when (logbitp b y) (setq z (logxor z (ash x b)))))
622 // (when (zerop (mod y 8)) (format t "~% "))
623 // (format t " 0x~3,'0X," z))))
626 // Multiply two GF2-polynomials of degree < 16.
627 #if defined(__sparc__) || defined(__sparc64__)
628 extern "C" uint32 gf2_mul16 (uint16 x, uint16 y);
630 uint32 gf2_mul16 (uint16 x, uint16 y)
632 var uint16 *ptr; // uint16 ptr[0x10];
635 ptr = gf2_mul_table[x & 0xFF];
636 res ^= (uint32)ptr[y & 0xF];
637 res ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
638 res ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
639 res ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
640 ptr = gf2_mul_table[(x >> 8) & 0xFF];
641 res ^= (uint32)ptr[y & 0xF] << 8;
642 res ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
643 res ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
644 res ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
649 // Multiply two GF2-polynomials of degree < 32.
650 // Stores the low part, returns the high part.
651 #if defined(__sparc__) || defined(__sparc64__)
652 extern "C" uint32 gf2_mul32 (uint32 x, uint32 y, uint32* plo);
654 uint32 gf2_mul32 (uint32 x, uint32 y, uint32* plo)
656 var uint16 *ptr; // uint16 ptr[0x10];
660 // Result will be (hi << 32) ^ (mid << 16) ^ (lo << 0).
662 // Standard multiplication, 32 table accesses.
663 ptr = gf2_mul_table[x & 0xFF];
664 lo ^= (uint32)ptr[y & 0xF];
665 lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
666 lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
667 lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
668 mid ^= (uint32)ptr[(y >> 16) & 0xF];
669 mid ^= (uint32)ptr[(y >> 20) & 0xF] << 4;
670 mid ^= (uint32)ptr[(y >> 24) & 0xF] << 8;
671 mid ^= (uint32)ptr[(y >> 28) & 0xF] << 12;
672 ptr = gf2_mul_table[(x >> 8) & 0xFF];
673 lo ^= (uint32)ptr[y & 0xF] << 8;
674 lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
675 mid ^= (uint32)ptr[(y >> 8) & 0xF];
676 mid ^= (uint32)ptr[(y >> 12) & 0xF] << 4;
677 mid ^= (uint32)ptr[(y >> 16) & 0xF] << 8;
678 mid ^= (uint32)ptr[(y >> 20) & 0xF] << 12;
679 hi ^= (uint32)ptr[(y >> 24) & 0xF];
680 hi ^= (uint32)ptr[(y >> 28) & 0xF] << 4;
681 ptr = gf2_mul_table[(x >> 16) & 0xFF];
682 mid ^= (uint32)ptr[y & 0xF];
683 mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
684 mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
685 mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
686 hi ^= (uint32)ptr[(y >> 16) & 0xF];
687 hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4;
688 hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8;
689 hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12;
690 ptr = gf2_mul_table[(x >> 24) & 0xFF];
691 mid ^= (uint32)ptr[y & 0xF] << 8;
692 mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
693 hi ^= (uint32)ptr[(y >> 8) & 0xF];
694 hi ^= (uint32)ptr[(y >> 12) & 0xF] << 4;
695 hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8;
696 hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12;
697 hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16;
698 hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20;
701 // lo := low16(x)*low16(y)
702 // hi := high16(x)*high16(y)
703 // mid := (high16(x)+low16(x))*(high16(y)+low16(y))
704 // mid := mid + lo + hi
705 // 24 table accesses.
706 ptr = gf2_mul_table[x & 0xFF];
707 lo ^= (uint32)ptr[y & 0xF];
708 lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
709 lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
710 lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
711 ptr = gf2_mul_table[(x >> 8) & 0xFF];
712 lo ^= (uint32)ptr[y & 0xF] << 8;
713 lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
714 lo ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
715 lo ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
716 ptr = gf2_mul_table[(x >> 16) & 0xFF];
717 hi ^= (uint32)ptr[(y >> 16) & 0xF];
718 hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4;
719 hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8;
720 hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12;
721 ptr = gf2_mul_table[(x >> 24) & 0xFF];
722 hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8;
723 hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12;
724 hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16;
725 hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20;
728 ptr = gf2_mul_table[x & 0xFF];
729 mid ^= (uint32)ptr[y & 0xF];
730 mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
731 mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
732 mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
733 ptr = gf2_mul_table[(x >> 8) & 0xFF];
734 mid ^= (uint32)ptr[y & 0xF] << 8;
735 mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
736 mid ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
737 mid ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
741 *plo = lo ^ (mid << 16);
742 return hi ^ (mid >> 16);
746 // Multiply two GF2-polynomials of degree < intDsize.
747 // Stores the low part, returns the high part.
749 #define gf2_mul_uintD gf2_mul32
752 inline uint64 gf2_mul32_ (uint32 x, uint32 y)
754 var uint16 *ptr; // uint16 ptr[0x10];
758 // Result will be (hi << 32) ^ (mid << 16) ^ (lo << 0).
760 // lo := low16(x)*low16(y)
761 // hi := high16(x)*high16(y)
762 // mid := (high16(x)+low16(x))*(high16(y)+low16(y))
763 // mid := mid + lo + hi
764 // 24 table accesses.
765 ptr = gf2_mul_table[x & 0xFF];
766 lo ^= (uint32)ptr[y & 0xF];
767 lo ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
768 lo ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
769 lo ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
770 ptr = gf2_mul_table[(x >> 8) & 0xFF];
771 lo ^= (uint32)ptr[y & 0xF] << 8;
772 lo ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
773 lo ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
774 lo ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
775 ptr = gf2_mul_table[(x >> 16) & 0xFF];
776 hi ^= (uint32)ptr[(y >> 16) & 0xF];
777 hi ^= (uint32)ptr[(y >> 20) & 0xF] << 4;
778 hi ^= (uint32)ptr[(y >> 24) & 0xF] << 8;
779 hi ^= (uint32)ptr[(y >> 28) & 0xF] << 12;
780 ptr = gf2_mul_table[(x >> 24) & 0xFF];
781 hi ^= (uint32)ptr[(y >> 16) & 0xF] << 8;
782 hi ^= (uint32)ptr[(y >> 20) & 0xF] << 12;
783 hi ^= (uint32)ptr[(y >> 24) & 0xF] << 16;
784 hi ^= (uint32)ptr[(y >> 28) & 0xF] << 20;
787 ptr = gf2_mul_table[x & 0xFF];
788 mid ^= (uint32)ptr[y & 0xF];
789 mid ^= (uint32)ptr[(y >> 4) & 0xF] << 4;
790 mid ^= (uint32)ptr[(y >> 8) & 0xF] << 8;
791 mid ^= (uint32)ptr[(y >> 12) & 0xF] << 12;
792 ptr = gf2_mul_table[(x >> 8) & 0xFF];
793 mid ^= (uint32)ptr[y & 0xF] << 8;
794 mid ^= (uint32)ptr[(y >> 4) & 0xF] << 12;
795 mid ^= (uint32)ptr[(y >> 8) & 0xF] << 16;
796 mid ^= (uint32)ptr[(y >> 12) & 0xF] << 20;
799 return (((uint64)hi << 32) | ((uint64)lo)) ^ ((uint64)mid << 16);
801 static uintD gf2_mul_uintD (uintD x, uintD y, uintD* plo)
804 // lo := low32(x)*low32(y)
805 // hi := high32(x)*high32(y)
806 // mid := (high32(x)+low32(x))*(high32(y)+low32(y))
807 // mid := mid + lo + hi
808 // 72 table accesses.
809 var uint64 lo = gf2_mul32_(x,y);
810 var uint64 hi = gf2_mul32_(x>>32,y>>32);
811 var uint64 mid = gf2_mul32_(x^(x>>32),y^(y>>32));
812 // Result will be (hi << 64) ^ (mid << 32) ^ (lo << 0).
813 *plo = lo ^ (mid << 32);
814 return hi ^ (mid >> 32);
818 static const _cl_UP gf2_mul (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const _cl_UP& y)
820 DeclarePoly(cl_GV_MI,x);
821 DeclarePoly(cl_GV_MI,y);
822 var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
823 var const cl_heap_GV_I_bits1 * yv = (const cl_heap_GV_I_bits1 *) y.heappointer;
824 var uintL xlen = xv->v.length();
825 var uintL ylen = yv->v.length();
827 return _cl_UP(UPR, x);
829 return _cl_UP(UPR, y);
830 var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
831 var uintL len = xlen+ylen-1;
832 var cl_GV_MI result = cl_GV_MI(len,R);
833 var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
834 xlen = ceiling(xlen,intDsize);
835 ylen = ceiling(ylen,intDsize);
837 var uintL xlen1 = ceiling(len,intDsize)-ylen; // = xlen-{0,1}
838 for (uintL i = 0; i < xlen; i++) {
839 var uintD xw = xv->data[i];
840 var uintD* rvptr = &rv->data[i];
842 for (uintL j = 0; j < ylen; j++) {
845 = gf2_mul_uintD(xw,yv->data[j],&rwlo);
846 *rvptr++ ^= carry ^ rwlo;
853 var uintL ylen1 = ceiling(len,intDsize)-xlen; // = ylen-{0,1}
854 for (uintL j = 0; j < ylen; j++) {
855 var uintD yw = yv->data[j];
856 var uintD* rvptr = &rv->data[j];
858 for (uintL i = 0; i < xlen; i++) {
861 = gf2_mul_uintD(xv->data[i],yw,&rwlo);
862 *rvptr++ ^= carry ^ rwlo;
869 return _cl_UP(UPR, result);
872 // In characteristic 2, we square a polynomial by doubling the exponents:
873 // (sum(a_i T^i))^2 = sum(a_i^2 T^2i) = sum(a_i T^2i).
875 static uint16 gf2_square_table[0x100] =
877 0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
878 0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
879 0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
880 0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
881 0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
882 0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
883 0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
884 0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
885 0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
886 0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
887 0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
888 0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
889 0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
890 0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
891 0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
892 0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
893 0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
894 0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
895 0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
896 0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
897 0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
898 0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
899 0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
900 0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
901 0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
902 0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
903 0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
904 0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
905 0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
906 0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
907 0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
908 0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
910 // Generated in CLISP:
913 // (dotimes (b 8) (when (logbitp b i) (setq j (logior j (ash 1 (+ b b))))))
914 // (when (zerop (mod i 8)) (format t "~% "))
915 // (format t " 0x~4,'0X," j)))
917 // Square a GF2-polynomial of degree < intDsize.
918 // Stores the low part, returns the high part.
919 static uintD gf2_square_uintD (uintD x, uintD* lo)
922 *lo = ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16)
923 | (uintD)gf2_square_table[x & 0xFF];
925 return ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16)
926 | (uintD)gf2_square_table[x & 0xFF];
929 *lo = ((uintD)gf2_square_table[(x>>24) & 0xFF] << 48)
930 | ((uintD)gf2_square_table[(x>>16) & 0xFF] << 32)
931 | ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16)
932 | (uintD)gf2_square_table[x & 0xFF];
934 return ((uintD)gf2_square_table[(x>>24) & 0xFF] << 48)
935 | ((uintD)gf2_square_table[(x>>16) & 0xFF] << 32)
936 | ((uintD)gf2_square_table[(x>>8) & 0xFF] << 16)
937 | (uintD)gf2_square_table[x & 0xFF];
941 static const _cl_UP gf2_square (cl_heap_univpoly_ring* UPR, const _cl_UP& x)
943 DeclarePoly(cl_GV_MI,x);
944 var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
945 var uintL xlen = xv->v.length();
947 return _cl_UP(UPR, x);
948 var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
949 var uintL len = 2*xlen-1;
950 var cl_GV_MI result = cl_GV_MI(len,R);
951 var cl_heap_GV_I_bits1 * rv = (cl_heap_GV_I_bits1 *) result.heappointer;
952 var uintL count = floor(xlen,intDsize);
953 for (uintL i = 0; i < count; i++)
954 rv->data[2*i+1] = gf2_square_uintD(xv->data[i],&rv->data[2*i]);
955 xlen = xlen%intDsize;
957 var uintD hiword = xv->data[count]; // xlen bits
958 hiword = gf2_square_uintD(hiword,&rv->data[2*count]);
959 if (xlen > intDsize/2)
960 rv->data[2*count+1] = hiword;
962 return _cl_UP(UPR, result);
965 // Scalar multiplication of GF(2)-polynomials is trivial: 0*y = 0, 1*y = y.
966 static const _cl_UP gf2_scalmul (cl_heap_univpoly_ring* UPR, const cl_ring_element& x, const _cl_UP& y)
968 if (!(UPR->basering() == x.ring())) cl_abort();
970 DeclarePoly(_cl_MI,x);
971 var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
973 return _cl_UP(UPR, cl_null_GV_I);
977 // Evaluation of GF(2)-polynomials is trivial:
978 // At 0, it's the coefficient 0. At 1, it's the sum of all coefficients,
979 // i.e. the parity of the number of nonzero coefficients.
980 static const cl_ring_element gf2_eval (cl_heap_univpoly_ring* UPR, const _cl_UP& x, const cl_ring_element& y)
982 DeclarePoly(cl_GV_MI,x);
983 if (!(UPR->basering() == y.ring())) cl_abort();
984 { DeclarePoly(_cl_MI,y);
985 var cl_heap_modint_ring* R = TheModintRing(UPR->basering());
986 var const cl_heap_GV_I_bits1 * xv = (const cl_heap_GV_I_bits1 *) x.heappointer;
987 var uintL len = xv->v.length();
991 return cl_MI(R, x[0]);
993 var uintL count = ceiling(len,intDsize);
994 var uintL bitcount = 0;
997 bitcount += logcountD(xv->data[count]);
999 return R->canonhom(bitcount%2);
1003 static cl_univpoly_setops gf2_setops = {
1008 static cl_univpoly_addops gf2_addops = {
1016 static cl_univpoly_mulops gf2_mulops = {
1024 static cl_univpoly_modulops gf2_modulops = {
1028 static cl_univpoly_polyops gf2_polyops = {
1038 class cl_heap_gf2_univpoly_ring : public cl_heap_univpoly_ring {
1039 SUBCLASS_cl_heap_univpoly_ring()
1042 cl_heap_gf2_univpoly_ring (const cl_ring& r)
1043 : cl_heap_univpoly_ring (r, &gf2_setops, &gf2_addops, &gf2_mulops, &gf2_modulops, &gf2_polyops) {}