![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to gfmul.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [truecrypt] / truecrypt / common|
Return to gfmul.c CVS log | Up to [truecrypt] / truecrypt / common |
1.1 root 1: /*
2: ---------------------------------------------------------------------------
3: Copyright (c) 2003, Dr Brian Gladman, Worcester, UK. All rights reserved.
4:
5: LICENSE TERMS
6:
7: The free distribution and use of this software in both source and binary
8: form is allowed (with or without changes) provided that:
9:
10: 1. distributions of this source code include the above copyright
11: notice, this list of conditions and the following disclaimer;
12:
13: 2. distributions in binary form include the above copyright
14: notice, this list of conditions and the following disclaimer
15: in the documentation and/or other associated materials;
16:
17: 3. the copyright holder's name is not used to endorse products
18: built using this software without specific written permission.
19:
20: ALTERNATIVELY, provided that this notice is retained in full, this product
21: may be distributed under the terms of the GNU General Public License (GPL),
22: in which case the provisions of the GPL apply INSTEAD OF those given above.
23:
24: DISCLAIMER
25:
26: This software is provided 'as is' with no explicit or implied warranties
27: in respect of its properties, including, but not limited to, correctness
28: and/or fitness for purpose.
29: ---------------------------------------------------------------------------
30: Issue Date: 31/01/2004
31:
32: My thanks to John Viega and David McGrew for their support in developing
33: this code and to David for testing it on a big-endain system.
34: */
35:
36: /*
37: TrueCrypt Foundation made the following changes:
38:
39: - Added multiplication in the finite field GF(2^128) optimized for
40: cases involving a 64-bit operand.
41:
42: - Added multiplication in the finite field GF(2^64).
43:
44: - Added MSB-first mode.
45:
1.1.1.2 ! root 46: - Added basic test algorithms.
! 47:
1.1 root 48: - Removed GCM.
49: */
50:
51: #ifdef LINUX_DRIVER
52: #include <linux/module.h>
53: #include <linux/string.h>
54: #else
55: #include <memory.h>
56: #endif
57:
58: #include "GfMul.h"
59: #include "Tcdefs.h"
60: #include "Endian.h"
61:
62: /* BUFFER_ALIGN32 or BUFFER_ALIGN64 must be defined at this point to */
63: /* enable faster operation by taking advantage of memory aligned values */
64: /* NOTE: the BUFFER_ALIGN64 option has not been tested extensively */
65:
66: #define BUFFER_ALIGN32
67: #define UNROLL_LOOPS /* define to unroll some loops */
68: #define IN_LINES /* define to use inline functions */
69: /* in place of macros */
70:
71: #define mode(x) GM_##x
72:
73: #if defined(__cplusplus)
74: extern "C"
75: {
76: #endif
77:
78: typedef unsigned __int32 mode(32t);
79: typedef unsigned __int64 mode(64t);
80:
81: #define BRG_LITTLE_ENDIAN 1234 /* byte 0 is least significant (i386) */
82: #define BRG_BIG_ENDIAN 4321 /* byte 0 is most significant (mc68k) */
83:
84: #if BYTE_ORDER == LITTLE_ENDIAN
85: # define PLATFORM_BYTE_ORDER BRG_LITTLE_ENDIAN
86: #endif
87:
88: #if BYTE_ORDER == BIG_ENDIAN
89: # define PLATFORM_BYTE_ORDER BRG_BIG_ENDIAN
90: #endif
91:
92: #ifdef _MSC_VER
93: #pragma intrinsic(memcpy)
94: #define in_line __inline
95: #else
96: #define in_line
97: #endif
98:
99: #if 0 && defined(_MSC_VER)
100: #define rotl32 _lrotl
101: #define rotr32 _lrotr
102: #else
103: #define rotl32(x,n) (((x) << n) | ((x) >> (32 - n)))
104: #define rotr32(x,n) (((x) >> n) | ((x) << (32 - n)))
105: #endif
106:
107: #if !defined(bswap_32)
108: #define bswap_32(x) (rotr32((x), 24) & 0x00ff00ff | rotr32((x), 8) & 0xff00ff00)
109: #endif
110:
111: #if (PLATFORM_BYTE_ORDER == BRG_LITTLE_ENDIAN)
112: #define SWAP_BYTES
113: #else
114: #undef SWAP_BYTES
115: #endif
116:
117: #if defined(SWAP_BYTES)
118:
119: #if defined ( IN_LINES )
120:
121: in_line void bsw_32(void * p, unsigned int n)
122: { unsigned int i = n;
123: while(i--)
124: ((mode(32t)*)p)[i] = bswap_32(((mode(32t)*)p)[i]);
125: }
126:
127: #else
128:
129: #define bsw_32(p,n) \
130: { int _i = (n); while(_i--) ((mode(32t)*)p)[_i] = bswap_32(((mode(32t)*)p)[_i]); }
131:
132: #endif
133:
134: #else
135: #define bsw_32(p,n)
136: #endif
137:
138: /* These values are used to detect long word alignment in order */
139: /* to speed up some GCM buffer operations. This facility may */
140: /* not work on some machines */
141:
142: #define lp08(x) ((unsigned char*)(x))
143: #define lp32(x) ((mode(32t)*)(x))
144: #define lp64(x) ((mode(64t)*)(x))
145:
146: #define A32_MASK 3
147: #define A64_MASK 7
148: #define aligned32(x) (!(((mode(32t))(x)) & A32_MASK))
149: #define aligned64(x) (!(((mode(32t))(x)) & A64_MASK))
150:
151: #if defined( BUFFER_ALIGN32 )
152:
153: #define ADR_MASK A32_MASK
154: #define aligned aligned32
155: #define lp lp32
156: #define lp_inc 4
157:
158: #if defined( IN_LINES )
159:
160: in_line void move_block_aligned( void *p, const void *q)
161: {
162: lp32(p)[0] = lp32(q)[0], lp32(p)[1] = lp32(q)[1],
163: lp32(p)[2] = lp32(q)[2], lp32(p)[3] = lp32(q)[3];
164: }
165:
166: in_line void move_block_aligned64( void *p, const void *q)
167: {
168: lp32(p)[0] = lp32(q)[0], lp32(p)[1] = lp32(q)[1];
169: }
170:
171: in_line void xor_block_aligned( void *p, const void *q)
172: {
173: lp32(p)[0] ^= lp32(q)[0], lp32(p)[1] ^= lp32(q)[1],
174: lp32(p)[2] ^= lp32(q)[2], lp32(p)[3] ^= lp32(q)[3];
175: }
176:
177: in_line void xor_block_aligned64( void *p, const void *q)
178: {
179: lp32(p)[0] ^= lp32(q)[0], lp32(p)[1] ^= lp32(q)[1];
180: }
181:
182: #else
183:
184: #define move_block_aligned(p,q) \
185: lp32(p)[0] = lp32(q)[0], lp32(p)[1] = lp32(q)[1], \
186: lp32(p)[2] = lp32(q)[2], lp32(p)[3] = lp32(q)[3]
187:
188: #define xor_block_aligned(p,q) \
189: lp32(p)[0] ^= lp32(q)[0], lp32(p)[1] ^= lp32(q)[1], \
190: lp32(p)[2] ^= lp32(q)[2], lp32(p)[3] ^= lp32(q)[3]
191:
192: #endif
193:
194: #elif defined( BUFFER_ALIGN64 )
195:
196: #define ADR_MASK A64_MASK
197: #define aligned aligned64
198: #define lp lp64
199: #define lp_inc 8
200:
201: #define move_block_aligned(p,q) \
202: lp64(p)[0] = lp64(q)[0], lp64(p)[1] = lp64(q)[1]
203:
204: #define xor_block_aligned(p,q) \
205: lp64(p)[0] ^= lp64(q)[0], lp64(p)[1] ^= lp64(q)[1]
206:
207: #else
208: #define aligned(x) 0
209: #endif
210:
211: #define move_block(p,q) memcpy((p), (q), BLOCK_LEN)
212:
213: #define xor_block(p,q) \
214: lp08(p)[ 0] ^= lp08(q)[ 0], lp08(p)[ 1] ^= lp08(q)[ 1], \
215: lp08(p)[ 2] ^= lp08(q)[ 2], lp08(p)[ 3] ^= lp08(q)[ 3], \
216: lp08(p)[ 4] ^= lp08(q)[ 4], lp08(p)[ 5] ^= lp08(q)[ 5], \
217: lp08(p)[ 6] ^= lp08(q)[ 6], lp08(p)[ 7] ^= lp08(q)[ 7], \
218: lp08(p)[ 8] ^= lp08(q)[ 8], lp08(p)[ 9] ^= lp08(q)[ 9], \
219: lp08(p)[10] ^= lp08(q)[10], lp08(p)[11] ^= lp08(q)[11], \
220: lp08(p)[12] ^= lp08(q)[12], lp08(p)[13] ^= lp08(q)[13], \
221: lp08(p)[14] ^= lp08(q)[14], lp08(p)[15] ^= lp08(q)[15]
222:
223:
224: #define gf_dat(q) {\
225: q(0x00), q(0x01), q(0x02), q(0x03), q(0x04), q(0x05), q(0x06), q(0x07),\
226: q(0x08), q(0x09), q(0x0a), q(0x0b), q(0x0c), q(0x0d), q(0x0e), q(0x0f),\
227: q(0x10), q(0x11), q(0x12), q(0x13), q(0x14), q(0x15), q(0x16), q(0x17),\
228: q(0x18), q(0x19), q(0x1a), q(0x1b), q(0x1c), q(0x1d), q(0x1e), q(0x1f),\
229: q(0x20), q(0x21), q(0x22), q(0x23), q(0x24), q(0x25), q(0x26), q(0x27),\
230: q(0x28), q(0x29), q(0x2a), q(0x2b), q(0x2c), q(0x2d), q(0x2e), q(0x2f),\
231: q(0x30), q(0x31), q(0x32), q(0x33), q(0x34), q(0x35), q(0x36), q(0x37),\
232: q(0x38), q(0x39), q(0x3a), q(0x3b), q(0x3c), q(0x3d), q(0x3e), q(0x3f),\
233: q(0x40), q(0x41), q(0x42), q(0x43), q(0x44), q(0x45), q(0x46), q(0x47),\
234: q(0x48), q(0x49), q(0x4a), q(0x4b), q(0x4c), q(0x4d), q(0x4e), q(0x4f),\
235: q(0x50), q(0x51), q(0x52), q(0x53), q(0x54), q(0x55), q(0x56), q(0x57),\
236: q(0x58), q(0x59), q(0x5a), q(0x5b), q(0x5c), q(0x5d), q(0x5e), q(0x5f),\
237: q(0x60), q(0x61), q(0x62), q(0x63), q(0x64), q(0x65), q(0x66), q(0x67),\
238: q(0x68), q(0x69), q(0x6a), q(0x6b), q(0x6c), q(0x6d), q(0x6e), q(0x6f),\
239: q(0x70), q(0x71), q(0x72), q(0x73), q(0x74), q(0x75), q(0x76), q(0x77),\
240: q(0x78), q(0x79), q(0x7a), q(0x7b), q(0x7c), q(0x7d), q(0x7e), q(0x7f),\
241: q(0x80), q(0x81), q(0x82), q(0x83), q(0x84), q(0x85), q(0x86), q(0x87),\
242: q(0x88), q(0x89), q(0x8a), q(0x8b), q(0x8c), q(0x8d), q(0x8e), q(0x8f),\
243: q(0x90), q(0x91), q(0x92), q(0x93), q(0x94), q(0x95), q(0x96), q(0x97),\
244: q(0x98), q(0x99), q(0x9a), q(0x9b), q(0x9c), q(0x9d), q(0x9e), q(0x9f),\
245: q(0xa0), q(0xa1), q(0xa2), q(0xa3), q(0xa4), q(0xa5), q(0xa6), q(0xa7),\
246: q(0xa8), q(0xa9), q(0xaa), q(0xab), q(0xac), q(0xad), q(0xae), q(0xaf),\
247: q(0xb0), q(0xb1), q(0xb2), q(0xb3), q(0xb4), q(0xb5), q(0xb6), q(0xb7),\
248: q(0xb8), q(0xb9), q(0xba), q(0xbb), q(0xbc), q(0xbd), q(0xbe), q(0xbf),\
249: q(0xc0), q(0xc1), q(0xc2), q(0xc3), q(0xc4), q(0xc5), q(0xc6), q(0xc7),\
250: q(0xc8), q(0xc9), q(0xca), q(0xcb), q(0xcc), q(0xcd), q(0xce), q(0xcf),\
251: q(0xd0), q(0xd1), q(0xd2), q(0xd3), q(0xd4), q(0xd5), q(0xd6), q(0xd7),\
252: q(0xd8), q(0xd9), q(0xda), q(0xdb), q(0xdc), q(0xdd), q(0xde), q(0xdf),\
253: q(0xe0), q(0xe1), q(0xe2), q(0xe3), q(0xe4), q(0xe5), q(0xe6), q(0xe7),\
254: q(0xe8), q(0xe9), q(0xea), q(0xeb), q(0xec), q(0xed), q(0xee), q(0xef),\
255: q(0xf0), q(0xf1), q(0xf2), q(0xf3), q(0xf4), q(0xf5), q(0xf6), q(0xf7),\
256: q(0xf8), q(0xf9), q(0xfa), q(0xfb), q(0xfc), q(0xfd), q(0xfe), q(0xff) }
257:
258: /* given the value i in 0..255 as the byte overflow when a a field */
259: /* element in GHASH is multipled by x^8, this function will return */
260: /* the values that are generated in the lo 16-bit word of the field */
261: /* value by applying the modular polynomial. The values lo_byte and */
262: /* hi_byte are returned via the macro xp_fun(lo_byte, hi_byte) so */
263: /* that the values can be assembled into memory as required by a */
264: /* suitable definition of this macro operating on the table above */
265:
266: #define xp(i) xp_fun( \
267: (i & 0x80 ? 0xe1 : 0) ^ (i & 0x40 ? 0x70 : 0) ^ \
268: (i & 0x20 ? 0x38 : 0) ^ (i & 0x10 ? 0x1c : 0) ^ \
269: (i & 0x08 ? 0x0e : 0) ^ (i & 0x04 ? 0x07 : 0) ^ \
270: (i & 0x02 ? 0x03 : 0) ^ (i & 0x01 ? 0x01 : 0), \
271: (i & 0x80 ? 0x00 : 0) ^ (i & 0x40 ? 0x80 : 0) ^ \
272: (i & 0x20 ? 0x40 : 0) ^ (i & 0x10 ? 0x20 : 0) ^ \
273: (i & 0x08 ? 0x10 : 0) ^ (i & 0x04 ? 0x08 : 0) ^ \
274: (i & 0x02 ? 0x84 : 0) ^ (i & 0x01 ? 0xc2 : 0) )
275:
276: #define xp64(i) xp_fun( \
277: (i & 0x80 ? 0xd8 : 0) ^ (i & 0x40 ? 0x6c : 0) ^ \
278: (i & 0x20 ? 0x36 : 0) ^ (i & 0x10 ? 0x1b : 0) ^ \
279: (i & 0x08 ? 0x0d : 0) ^ (i & 0x04 ? 0x06 : 0) ^ \
280: (i & 0x02 ? 0x03 : 0) ^ (i & 0x01 ? 0x01 : 0), \
281: (i & 0x80 ? 0x00 : 0) ^ (i & 0x40 ? 0x00 : 0) ^ \
282: (i & 0x20 ? 0x00 : 0) ^ (i & 0x10 ? 0x00 : 0) ^ \
283: (i & 0x08 ? 0x80 : 0) ^ (i & 0x04 ? 0xc0 : 0) ^ \
284: (i & 0x02 ? 0x60 : 0) ^ (i & 0x01 ? 0xb0 : 0) )
285:
286: static mode(32t) gf_poly[2] = { 0, 0xe1000000 };
287: static mode(32t) gf_poly64[2] = { 0, 0xd8000000 };
288:
289: /* Multiply of a GF128 field element by x. The field element */
290: /* is held in an array of bytes in which field bits 8n..8n + 7 */
291: /* are held in byte[n], with lower indexed bits placed in the */
292: /* more numerically significant bit positions in bytes. */
293:
294: /* This function multiples a field element x, in the polynomial */
295: /* field representation. It uses 32-bit word operations to gain */
296: /* speed but compensates for machine endianess and hence works */
297: /* correctly on both styles of machine */
298:
299: in_line void mul_x(mode(32t) x[4])
300: { mode(32t) t;
301:
302: bsw_32(x, 4);
303:
304: /* at this point the filed element bits 0..127 are set out */
305: /* as follows in 32-bit words (where the most significant */
306: /* (ms) numeric bits are to the left) */
307: /* */
308: /* x[0] x[1] x[2] x[3] */
309: /* ms ls ms ls ms ls ms ls */
310: /* field: 0 ... 31 32 .. 63 64 .. 95 96 .. 127 */
311:
312: t = gf_poly[x[3] & 1]; /* bit 127 of the element */
313: x[3] = (x[3] >> 1) | (x[2] << 31); /* shift bits up by one */
314: x[2] = (x[2] >> 1) | (x[1] << 31); /* position */
315: x[1] = (x[1] >> 1) | (x[0] << 31); /* if bit 7 is 1 xor in */
316: x[0] = (x[0] >> 1) ^ t; /* the field polynomial */
317: bsw_32(x, 4);
318: }
319:
320: in_line void mul_x64(mode(32t) x[2])
321: { mode(32t) t;
322:
323: bsw_32(x, 2);
324:
325: /* at this point the filed element bits 0..127 are set out */
326: /* as follows in 32-bit words (where the most significant */
327: /* (ms) numeric bits are to the left) */
328: /* */
329: /* x[0] x[1] x[2] x[3] */
330: /* ms ls ms ls ms ls ms ls */
331: /* field: 0 ... 31 32 .. 63 64 .. 95 96 .. 127 */
332:
333: t = gf_poly64[x[1] & 1]; /* bit 127 of the element */
334: /* shift bits up by one */
335: /* position */
336: x[1] = (x[1] >> 1) | (x[0] << 31); /* if bit 7 is 1 xor in */
337: x[0] = (x[0] >> 1) ^ t; /* the field polynomial */
338: bsw_32(x, 2);
339: }
340:
341: /* Multiply of a GF128 field element by x^8 using 32-bit words */
342: /* for speed - machine endianess matters here */
343:
344: #if (PLATFORM_BYTE_ORDER == BRG_LITTLE_ENDIAN)
345:
346: #define xp_fun(x,y) ((mode(32t))(x)) | (((mode(32t))(y)) << 8)
347: static const unsigned __int16 gft_le[256] = gf_dat(xp);
348: static const unsigned __int16 gft_le64[256] = gf_dat(xp64);
349:
350: in_line void mul_lex8(mode(32t) x[4]) /* mutiply with long words */
351: { mode(32t) t = (x[3] >> 24); /* in little endian format */
352: x[3] = (x[3] << 8) | (x[2] >> 24);
353: x[2] = (x[2] << 8) | (x[1] >> 24);
354: x[1] = (x[1] << 8) | (x[0] >> 24);
355: x[0] = (x[0] << 8) ^ gft_le[t];
356: }
357:
358: in_line void mul_lex8_64(mode(32t) x[2]) /* mutiply with long words */
359: { mode(32t) t = (x[1] >> 24); /* in little endian format */
360: x[1] = (x[1] << 8) | (x[0] >> 24);
361: x[0] = (x[0] << 8) ^ gft_le64[t];
362: }
363:
364: #endif
365:
366: #if 1 || (PLATFORM_BYTE_ORDER == BRG_LITTLE_ENDIAN)
367:
368: #undef xp_fun
369: #define xp_fun(x,y) ((mode(32t))(y)) | (((mode(32t))(x)) << 8)
370: static const unsigned __int16 gft_be[256] = gf_dat(xp);
371: static const unsigned __int16 gft_be64[256] = gf_dat(xp64);
372:
373: in_line void mul_bex8(mode(32t) x[4]) /* mutiply with long words */
374: { mode(32t) t = (x[3] & 0xff); /* in big endian format */
375: x[3] = (x[3] >> 8) | (x[2] << 24);
376: x[2] = (x[2] >> 8) | (x[1] << 24);
377: x[1] = (x[1] >> 8) | (x[0] << 24);
378: x[0] = (x[0] >> 8) ^ (((mode(32t))gft_be[t]) << 16);
379: }
380:
381: in_line void mul_bex8_64(mode(32t) x[2]) /* mutiply with long words */
382: { mode(32t) t = (x[1] & 0xff); /* in big endian format */
383: x[1] = (x[1] >> 8) | (x[0] << 24);
384: x[0] = (x[0] >> 8) ^ (((mode(32t))gft_be64[t]) << 16);
385: }
386:
387: #endif
388:
389: /* hence choose the correct version for the machine endianess */
390:
391: #if PLATFORM_BYTE_ORDER == BRG_BIG_ENDIAN
392: #define mul_x8 mul_bex8
393: #define mul_x8_64 mul_bex8_64
394: #else
395: #define mul_x8 mul_lex8
396: #define mul_x8_64 mul_lex8_64
397: #endif
398:
399: /* different versions of the general gf_mul function are provided */
400: /* here. Sadly none are very fast :-( */
401:
402: void GfMul128 (void *a, const void* b)
403: { mode(32t) r[CBLK_LEN >> 2], p[8][CBLK_LEN >> 2];
404: int i;
405:
406: move_block_aligned(p[0], b);
407: bsw_32(p[0], 4);
408: for(i = 0; i < 7; ++i)
409: {
410: p[i + 1][3] = (p[i][3] >> 1) | (p[i][2] << 31);
411: p[i + 1][2] = (p[i][2] >> 1) | (p[i][1] << 31);
412: p[i + 1][1] = (p[i][1] >> 1) | (p[i][0] << 31);
413: p[i + 1][0] = (p[i][0] >> 1) ^ gf_poly[p[i][3] & 1];
414: }
415:
416: memset(r, 0, CBLK_LEN);
417: for(i = 0; i < 16; ++i)
418: {
419: if(i) mul_bex8(r); /* order is always big endian here */
420:
421: if(((unsigned char*)a)[15 - i] & 0x80)
422: xor_block_aligned(r, p[0]);
423: if(((unsigned char*)a)[15 - i] & 0x40)
424: xor_block_aligned(r, p[1]);
425: if(((unsigned char*)a)[15 - i] & 0x20)
426: xor_block_aligned(r, p[2]);
427: if(((unsigned char*)a)[15 - i] & 0x10)
428: xor_block_aligned(r, p[3]);
429: if(((unsigned char*)a)[15 - i] & 0x08)
430: xor_block_aligned(r, p[4]);
431: if(((unsigned char*)a)[15 - i] & 0x04)
432: xor_block_aligned(r, p[5]);
433: if(((unsigned char*)a)[15 - i] & 0x02)
434: xor_block_aligned(r, p[6]);
435: if(((unsigned char*)a)[15 - i] & 0x01)
436: xor_block_aligned(r, p[7]);
437: }
438: bsw_32(r, 4);
439: move_block_aligned(a, r);
440: }
441:
442: #if defined( UNROLL_LOOPS )
443:
444: #define xor_8k(i) \
445: xor_block_aligned(r, ctx->gf_t8k[i + i][a[i] & 15]); \
446: xor_block_aligned(r, ctx->gf_t8k[i + i + 1][a[i] >> 4])
447:
448:
449: void GfMul128Tab (unsigned char a[CBLK_LEN], GfCtx8k *ctx)
450: { unsigned __int32 r[CBLK_LEN >> 2];
451:
452: move_block_aligned(r, ctx->gf_t8k[0][a[0] & 15]);
453: xor_block_aligned(r, ctx->gf_t8k[1][a[0] >> 4]);
454: xor_8k( 1); xor_8k( 2); xor_8k( 3);
455: xor_8k( 4); xor_8k( 5); xor_8k( 6); xor_8k( 7);
456: xor_8k( 8); xor_8k( 9); xor_8k(10); xor_8k(11);
457: xor_8k(12); xor_8k(13); xor_8k(14); xor_8k(15);
458: move_block_aligned(a, r);
459: }
460:
461: #else
462:
463: void GfMul128Tab (unsigned char a[CBLK_LEN], GfCtx8k *ctx)
464: { unsigned __int32 r[CBLK_LEN >> 2], *p;
465: int i;
466:
467: p = ctx->gf_t8k[0][a[0] & 15];
468: memcpy(r, p, CBLK_LEN);
469: p = ctx->gf_t8k[1][a[0] >> 4];
470: xor_block_aligned(r, p);
471: for(i = 1; i < CBLK_LEN; ++i)
472: {
473: xor_block_aligned(r, ctx->gf_t8k[i + i][a[i] & 15]);
474: xor_block_aligned(r, ctx->gf_t8k[i + i + 1][a[i] >> 4]);
475: }
476: memcpy(a, r, CBLK_LEN);
477: }
478:
479: #endif
480:
481: void compile_8k_table(unsigned __int8 *a, GfCtx8k *ctx)
482: { int i, j, k;
483:
484: memset(ctx->gf_t8k, 0, 32 * 16 * 16);
485: for(i = 0; i < 2 * CBLK_LEN; ++i)
486: {
487: if(i == 0)
488: {
489: memcpy(ctx->gf_t8k[1][8], a, CBLK_LEN);
490: for(j = 4; j > 0; j >>= 1)
491: {
492: memcpy(ctx->gf_t8k[1][j], ctx->gf_t8k[1][j + j], CBLK_LEN);
493: mul_x(ctx->gf_t8k[1][j]);
494: }
495: memcpy(ctx->gf_t8k[0][8], ctx->gf_t8k[1][1], CBLK_LEN);
496: mul_x(ctx->gf_t8k[0][8]);
497: for(j = 4; j > 0; j >>= 1)
498: {
499: memcpy(ctx->gf_t8k[0][j], ctx->gf_t8k[0][j + j], CBLK_LEN);
500: mul_x(ctx->gf_t8k[0][j]);
501: }
502: }
503: else if(i > 1)
504: for(j = 8; j > 0; j >>= 1)
505: {
506: memcpy(ctx->gf_t8k[i][j], ctx->gf_t8k[i - 2][j], CBLK_LEN);
507: mul_x8(ctx->gf_t8k[i][j]);
508: }
509:
510: for(j = 2; j < 16; j += j)
511: {
512: mode(32t) *pj = ctx->gf_t8k[i][j];
513: mode(32t) *pk = ctx->gf_t8k[i][1];
514: mode(32t) *pl = ctx->gf_t8k[i][j + 1];
515:
516: for(k = 1; k < j; ++k)
517: {
518: *pl++ = pj[0] ^ *pk++;
519: *pl++ = pj[1] ^ *pk++;
520: *pl++ = pj[2] ^ *pk++;
521: *pl++ = pj[3] ^ *pk++;
522: }
523: }
524: }
525: }
526:
527:
528: void compile_4k_table64(unsigned __int8 *a, GfCtx4k64 *ctx)
529: { int i, j, k;
530:
531: memset(ctx->gf_t4k, 0, sizeof(ctx->gf_t4k));
532: for(i = 0; i < 2 * CBLK_LEN8; ++i)
533: {
534: if(i == 0)
535: {
536: memcpy(ctx->gf_t4k[1][8], a, CBLK_LEN8);
537: for(j = 4; j > 0; j >>= 1)
538: {
539: memcpy(ctx->gf_t4k[1][j], ctx->gf_t4k[1][j + j], CBLK_LEN8);
540: mul_x64(ctx->gf_t4k[1][j]);
541: }
542: memcpy(ctx->gf_t4k[0][8], ctx->gf_t4k[1][1], CBLK_LEN8);
543: mul_x64(ctx->gf_t4k[0][8]);
544: for(j = 4; j > 0; j >>= 1)
545: {
546: memcpy(ctx->gf_t4k[0][j], ctx->gf_t4k[0][j + j], CBLK_LEN8);
547: mul_x64(ctx->gf_t4k[0][j]);
548: }
549: }
550: else if(i > 1)
551: for(j = 8; j > 0; j >>= 1)
552: {
553: memcpy(ctx->gf_t4k[i][j], ctx->gf_t4k[i - 2][j], CBLK_LEN8);
554: mul_x8_64(ctx->gf_t4k[i][j]);
555: }
556:
557: for(j = 2; j < 16; j += j)
558: {
559: mode(32t) *pj = ctx->gf_t4k[i][j];
560: mode(32t) *pk = ctx->gf_t4k[i][1];
561: mode(32t) *pl = ctx->gf_t4k[i][j + 1];
562:
563: for(k = 1; k < j; ++k)
564: {
565: *pl++ = pj[0] ^ *pk++;
566: *pl++ = pj[1] ^ *pk++;
567: *pl++ = pj[2] ^ *pk++;
568: *pl++ = pj[3] ^ *pk++;
569: }
570: }
571: }
572: }
573:
574: static int IsBitSet128 (unsigned int bit, unsigned __int8 *a)
575: {
576: return a[(127 - bit) / 8] & (0x80 >> ((127 - bit) % 8));
577: }
578:
579: static int IsBitSet64 (unsigned int bit, unsigned __int8 *a)
580: {
581: return a[(63 - bit) / 8] & (0x80 >> ((63 - bit) % 8));
582: }
583:
584: static void SetBit128 (unsigned int bit, unsigned __int8 *a)
585: {
586: a[(127 - bit) / 8] |= 0x80 >> ((127 - bit) % 8);
587: }
588:
589: static void SetBit64 (unsigned int bit, unsigned __int8 *a)
590: {
591: a[(63 - bit) / 8] |= 0x80 >> ((63 - bit) % 8);
592: }
593:
1.1.1.2 ! root 594: void MirrorBits128 (unsigned __int8 *a)
1.1 root 595: {
596: unsigned __int8 t[128 / 8];
597: int i;
598: memset (t,0,16);
599: for (i = 0; i < 128; i++)
600: {
601: if (IsBitSet128(i, a))
602: SetBit128 (127 - i, t);
603: }
604: memcpy (a, t, sizeof (t));
605: burn (t,sizeof (t));
606: }
607:
608: void MirrorBits64 (unsigned __int8 *a)
609: {
610: unsigned __int8 t[64 / 8];
611: int i;
612: memset (t,0,8);
613: for (i = 0; i < 64; i++)
614: {
615: if (IsBitSet64(i, a))
616: SetBit64 (63 - i, t);
617: }
618: memcpy (a, t, sizeof (t));
619: burn (t,sizeof (t));
620: }
621:
622: /* Allocate and initialize speed optimization table
623: for multiplication by 64-bit operand in MSB-first mode */
624: int Gf128Tab64Init (unsigned __int8 *a, GfCtx *ctx)
625: {
626: GfCtx8k *ctx8k;
627: unsigned __int8 am[16];
628: int i, j;
629:
630: ctx8k = (GfCtx8k *) TCalloc (sizeof (GfCtx8k));
631: if (!ctx8k)
632: return FALSE;
633:
634: memcpy (am, a, 16);
635: MirrorBits128 (am);
636: compile_8k_table (am, ctx8k);
637:
638: /* Convert 8k LSB-first table to 4k MSB-first */
639: for (i = 16; i < 32; i++)
640: {
641: for (j = 0; j < 16; j++)
642: {
643: int jm = 0;
644: jm |= (j & 0x1) << 3;
645: jm |= (j & 0x2) << 1;
646: jm |= (j & 0x4) >> 1;
647: jm |= (j & 0x8) >> 3;
648:
649: memcpy (&ctx->gf_t128[i-16][jm], (unsigned char *)&ctx8k->gf_t8k[31-i][j], 16);
650: MirrorBits128 ((unsigned char *)&ctx->gf_t128[i-16][jm]);
651: }
652: }
653:
654: burn (ctx8k ,sizeof (*ctx8k));
655: burn (am, sizeof (am));
656: TCfree (ctx8k);
657: return TRUE;
658: }
659:
660: int Gf64TabInit (unsigned __int8 *a, GfCtx *ctx)
661: {
662: GfCtx4k64 *ctx4k;
663: unsigned __int8 am[8];
664: int i, j;
665:
666: ctx4k = (GfCtx4k64 *) TCalloc (sizeof (GfCtx4k64));
667: if (!ctx4k)
668: return FALSE;
669:
670: memcpy (am, a, 8);
671: MirrorBits64 (am);
672: compile_4k_table64 (am, ctx4k);
673:
674: /* Convert LSB-first table to MSB-first */
675: for (i = 0; i < 16; i++)
676: {
677: for (j = 0; j < 16; j++)
678: {
679: int jm = 0;
680: jm |= (j & 0x1) << 3;
681: jm |= (j & 0x2) << 1;
682: jm |= (j & 0x4) >> 1;
683: jm |= (j & 0x8) >> 3;
684:
685: memcpy (&ctx->gf_t64[i][jm], (unsigned char *)&ctx4k->gf_t4k[15-i][j], 8);
686: MirrorBits64 ((unsigned char *)&ctx->gf_t64[i][jm]);
687: }
688: }
689:
690: burn (ctx4k,sizeof (*ctx4k));
691: burn (am, sizeof (am));
692: TCfree (ctx4k);
693: return TRUE;
694: }
695:
696: #define xor_8kt64(i) \
697: xor_block_aligned(r, ctx->gf_t128[i + i][a[i] & 15]); \
698: xor_block_aligned(r, ctx->gf_t128[i + i + 1][a[i] >> 4])
699:
700: /* Multiply a 128-bit number by a 64-bit number in the finite field GF(2^128) */
701: void Gf128MulBy64Tab (unsigned __int8 a[8], unsigned __int8 p[16], GfCtx *ctx)
702: {
703: unsigned __int32 r[CBLK_LEN >> 2];
704:
705: move_block_aligned(r, ctx->gf_t128[7*2][a[7] & 15]);
706: xor_block_aligned(r, ctx->gf_t128[7*2+1][a[7] >> 4]);
707:
708: if (*(unsigned __int16 *)a)
709: {
710: xor_8kt64(0);
711: xor_8kt64(1);
712: }
713: if (a[2])
714: {
715: xor_8kt64(2);
716: }
717: xor_8kt64(3);
718: xor_8kt64(4);
719: xor_8kt64(5);
720: xor_8kt64(6);
721:
722: move_block_aligned(p, r);
723: }
724:
725: #define xor_8k64(i) \
726: xor_block_aligned64(r, ctx->gf_t64[i + i][a[i] & 15]); \
727: xor_block_aligned64(r, ctx->gf_t64[i + i + 1][a[i] >> 4])
728:
729: /* Multiply two 64-bit numbers in the finite field GF(2^64) */
730: void Gf64MulTab (unsigned char a[8], unsigned char p[8], GfCtx *ctx)
731: {
732: unsigned __int32 r[CBLK_LEN8 >> 2];
733:
734: move_block_aligned64(r, ctx->gf_t64[7*2][a[7] & 15]);
735: xor_block_aligned64(r, ctx->gf_t64[7*2+1][a[7] >> 4]);
736:
737: if (*(unsigned __int16 *)a)
738: {
739: xor_8k64(0);
740: xor_8k64(1);
741: }
742: if (a[2])
743: {
744: xor_8k64(2);
745: }
746: xor_8k64(3);
747: xor_8k64(4);
748: xor_8k64(5);
749: xor_8k64(6);
750:
751: move_block_aligned64(p, r);
752: }
753:
754:
755: /* Basic algorithms for testing of optimized algorithms */
756:
757: static void xor128 (unsigned __int64 *a, unsigned __int64 *b)
758: {
759: *a++ ^= *b++;
760: *a ^= *b;
761: }
762:
763: static void shl128 (unsigned __int8 *a)
764: {
765: int i, x = 0, xx;
766: for (i = 15; i >= 0; i--)
767: {
768: xx = (a[i] & 0x80) >> 7;
769: a[i] = (a[i] << 1) | x;
770: x = xx;
771: }
772: }
773:
774: static void GfMul128Basic (unsigned __int8 *a, unsigned __int8 *b, unsigned __int8 *p)
775: {
776: int i;
777: unsigned __int8 la[16];
778: memcpy (la, a, 16);
779: memset (p, 0, 16);
780:
781: for (i = 0; i < 128; i++)
782: {
783: if (IsBitSet128 (i, b))
784: xor128 ((unsigned __int64 *)p, (unsigned __int64 *)la);
785:
786: if (la[0] & 0x80)
787: {
788: shl128 (la);
789: la[15] ^= 0x87;
790: }
791: else
792: {
793: shl128 (la);
794: }
795: }
796: }
797:
798: static void xor64 (unsigned __int64 *a, unsigned __int64 *b)
799: {
800: *a ^= *b;
801: }
802:
803: static void shl64 (unsigned __int8 *a)
804: {
805: int i, x = 0, xx;
806: for (i = 7; i >= 0; i--)
807: {
808: xx = (a[i] & 0x80) >> 7;
809: a[i] = (a[i] << 1) | x;
810: x = xx;
811: }
812: }
813:
814: static void GfMul64Basic (unsigned __int8 *a, unsigned __int8 *b, unsigned __int8* p)
815: {
816: int i;
817: unsigned __int8 la[8];
818: memcpy (la, a, 8);
819: memset (p, 0, 8);
820:
821: for (i = 0; i < 64; i++)
822: {
823: if (IsBitSet64 (i, b))
824: xor64 ((unsigned __int64 *)p, (unsigned __int64 *)la);
825:
826: if (la[0] & 0x80)
827: {
828: shl64 (la);
829: la[7] ^= 0x1b;
830: }
831: else
832: {
833: shl64 (la);
834: }
835: }
836: }
837:
838:
839: BOOL GfMulSelfTest ()
840: {
841: BOOL result = TRUE;
842: unsigned __int8 a[16];
843: unsigned __int8 b[16];
844: unsigned __int8 p1[16];
845: unsigned __int8 p2[16];
846: GfCtx *gfCtx = (GfCtx *) TCalloc (sizeof (GfCtx));
847: int i, j;
848:
849: if (!gfCtx)
850: return FALSE;
851:
852: /* GF(2^64) */
853: for (i = 0; i < 0x100; i++)
854: {
855: for (j = 0; j < 8; j++)
856: {
857: a[j] = (unsigned __int8) i;
858: b[j] = a[j] ^ 0xff;
859: }
860:
861: GfMul64Basic (a, b, p1);
862:
863: Gf64TabInit (a, gfCtx);
864: Gf64MulTab (b, p2, gfCtx);
865:
866: if (memcmp (p1, p2, 8) != 0)
867: result = FALSE;
868: }
869:
870: /* GF(2^128) */
871: for (i = 0; i < 0x100; i++)
872: {
873: for (j = 0; j < 16; j++)
874: {
875: a[j] = (unsigned __int8) i;
876: b[j] = j < 8 ? 0 : a[j] ^ 0xff;
877: }
878:
879: GfMul128Basic (a, b, p1);
880:
881: Gf128Tab64Init (a, gfCtx);
882: Gf128MulBy64Tab (b + 8, p2, gfCtx);
883:
884: if (memcmp (p1, p2, 16) != 0)
885: result = FALSE;
886: }
887:
888: TCfree (gfCtx);
889: return result;
890: }
891:
892: #if defined(__cplusplus)
893: }
894: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.