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