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