1 2 package st.ata.util; 3 4 import java.util.Hashtable ; 5 6 45 46 @SuppressWarnings ("unchecked") 48 public final class FPGenerator { 49 50 58 public static FPGenerator make(long polynomial, int degree) { 59 Long l = new Long (polynomial); 60 FPGenerator fpgen = (FPGenerator) generators.get(l); 61 if (fpgen == null) { 62 fpgen = new FPGenerator(polynomial, degree); 63 generators.put(l, fpgen); 64 } 65 return fpgen; 66 } 67 private static final Hashtable generators = new Hashtable (10); 68 69 private static final long zero = 0; 70 private static final long one = 0x8000000000000000L; 71 72 73 75 public long reduce(long fp) { 76 int N = (8 - degree/8); 77 long local = (N == 8 ? 0 : fp & (-1L << 8*N)); 78 long temp = zero; 79 for (int i = 0; i < N; i++) { 80 temp ^= ByteModTable[8+i][((int)fp) & 0xff]; 81 fp >>>= 8; 82 }; 83 return local ^ temp; 84 } 85 86 91 public long extend_byte(long f, int v) { 92 f ^= (0xff & v); 93 int i = (int)f; 94 long result = (f>>>8); 95 result ^= ByteModTable[7][i & 0xff]; 96 return result; 97 } 98 99 101 public long extend_char(long f, int v) { 102 f ^= (0xffff & v); 103 int i = (int)f; 104 long result = (f>>>16); 105 result ^= ByteModTable[6][i & 0xff]; i >>>= 8; 106 result ^= ByteModTable[7][i & 0xff]; 107 return result; 108 } 109 110 112 public long extend_int(long f, int v) { 113 f ^= (0xffffffffL & v); 114 int i = (int)f; 115 long result = (f>>>32); 116 result ^= ByteModTable[4][i & 0xff]; i >>>= 8; 117 result ^= ByteModTable[5][i & 0xff]; i >>>= 8; 118 result ^= ByteModTable[6][i & 0xff]; i >>>= 8; 119 result ^= ByteModTable[7][i & 0xff]; 120 return result; 121 } 122 123 125 public long extend_long(long f, long v) { 126 f ^= v; 127 long result = ByteModTable[0][(int)(f & 0xff)]; f >>>= 8; 128 result ^= ByteModTable[1][(int)(f & 0xff)]; f >>>= 8; 129 result ^= ByteModTable[2][(int)(f & 0xff)]; f >>>= 8; 130 result ^= ByteModTable[3][(int)(f & 0xff)]; f >>>= 8; 131 result ^= ByteModTable[4][(int)(f & 0xff)]; f >>>= 8; 132 result ^= ByteModTable[5][(int)(f & 0xff)]; f >>>= 8; 133 result ^= ByteModTable[6][(int)(f & 0xff)]; f >>>= 8; 134 result ^= ByteModTable[7][(int)(f & 0xff)]; 135 return result; 136 } 137 138 139 141 public long fp(byte[] buf, int start, int n) { 142 return extend(empty, buf, start, n); 143 } 144 145 147 public long fp(char[] buf, int start, int n) { 148 return extend(empty, buf, start, n); 149 } 150 151 157 public long fp(CharSequence s) { 158 return extend(empty, s); 159 } 160 161 163 public long fp(int[] buf, int start, int n) { 164 return extend(empty, buf, start, n); 165 } 166 167 169 public long fp(long[] buf, int start, int n) { 170 return extend(empty, buf, start, n); 171 } 172 173 175 public long fp8(String s) { 176 return extend8(empty, s); 177 } 178 179 182 public long fp8(char[] buf, int start, int n) { 183 return extend8(empty, buf, start, n); 184 } 185 186 187 189 public long extend(long f, byte v) { 190 return reduce(extend_byte(f, v)); 191 } 192 193 195 public long extend(long f, char v) { 196 return reduce(extend_char(f, v)); 197 } 198 199 201 public long extend(long f, int v) { 202 return reduce(extend_int(f, v)); 203 } 204 205 207 public long extend(long f, long v) { 208 return reduce(extend_long(f, v)); 209 } 210 211 215 public long extend(long f, byte[] buf, int start, int n) { 216 for (int i = 0; i < n; i++) { 217 f = extend_byte(f, buf[start+i]); 218 } 219 return reduce(f); 220 } 221 222 226 public long extend(long f, char[] buf, int start, int n) { 227 for (int i = 0; i < n; i++) { 228 f = extend_char(f, buf[start+i]); 229 } 230 return reduce(f); 231 } 232 233 236 public long extend(long f, CharSequence s) { 237 int n = s.length(); 238 for (int i = 0; i < n; i++) { 239 int v = (int) s.charAt(i); 240 f = extend_char(f, v); 241 } 242 return reduce(f); 243 } 244 245 252 253 257 public long extend(long f, int[] buf, int start, int n) { 258 for (int i = 0; i < n; i++) { 259 f = extend_int(f, buf[start+i]); 260 } 261 return reduce(f); 262 } 263 264 268 public long extend(long f, long[] buf, int start, int n) { 269 for (int i = 0; i < n; i++) { 270 f = extend_long(f, buf[start+i]); 271 } 272 return reduce(f); 273 } 274 275 278 public long extend8(long f, String s) { 279 int n = s.length(); 280 for (int i = 0; i < n; i++) { 281 int x = (int) s.charAt(i); 282 f = extend_byte(f, x); 283 } 284 return reduce(f); 285 } 286 287 291 public long extend8(long f, char[] buf, int start, int n) { 292 for (int i = 0; i < n; i++) { 293 f = extend_byte(f, buf[start+i]); 294 } 295 return reduce(f); 296 } 297 298 299 300 public final long empty; 301 302 304 public final int degree; 305 306 308 public long polynomial; 309 310 314 private long[][] ByteModTable; 315 316 322 private FPGenerator(long polynomial, int degree) { 323 this.degree = degree; 324 this.polynomial = polynomial; 325 ByteModTable = new long[16][256]; 326 327 long[] PowerTable = new long[128]; 328 329 long x_to_the_i = one; 330 long x_to_the_degree_minus_one = (one >>> (degree-1)); 331 for (int i = 0; i < 128; i++) { 332 PowerTable[i] = x_to_the_i; 336 boolean overflow = ((x_to_the_i & x_to_the_degree_minus_one) != 0); 337 x_to_the_i >>>= 1; 338 if (overflow) { 339 x_to_the_i ^= polynomial; 340 } 341 } 342 this.empty = PowerTable[64]; 343 344 for (int i = 0; i < 16; i++) { 345 for (int j = 0; j < 256; j++) { 348 long v = zero; 351 for (int k = 0; k < 8; k++) { 352 if ((j & (1 << k)) != 0) { 355 v ^= PowerTable[127 - i*8 - k]; 356 } 357 } 358 ByteModTable[i][j] = v; 359 } 360 } 361 } 362 363 368 public static final long polynomials[][] = { 369 null, 370 {0xC000000000000000L, 0xC000000000000000L}, 371 {0xE000000000000000L, 0xE000000000000000L}, 372 {0xD000000000000000L, 0xB000000000000000L}, 373 {0xF800000000000000L, 0xF800000000000000L}, 374 {0xEC00000000000000L, 0xBC00000000000000L}, 375 {0xDA00000000000000L, 0xB600000000000000L}, 376 {0xE500000000000000L, 0xE500000000000000L}, 377 {0x9680000000000000L, 0xD480000000000000L}, 378 {0x80C0000000000000L, 0x8840000000000000L}, 379 {0xB0A0000000000000L, 0xE9A0000000000000L}, 380 {0xD9F0000000000000L, 0xC9B0000000000000L}, 381 {0xE758000000000000L, 0xDE98000000000000L}, 382 {0xE42C000000000000L, 0x94E4000000000000L}, 383 {0xD4CE000000000000L, 0xB892000000000000L}, 384 {0xE2AB000000000000L, 0x9E39000000000000L}, 385 {0xCCE4800000000000L, 0x9783800000000000L}, 386 {0xD8F8C00000000000L, 0xA9CDC00000000000L}, 387 {0x9A28200000000000L, 0xFD79E00000000000L}, 388 {0xC782500000000000L, 0x96CD300000000000L}, 389 {0xBEE6880000000000L, 0xE902C80000000000L}, 390 {0x86D7E40000000000L, 0xF066340000000000L}, 391 {0x9888060000000000L, 0x910ABE0000000000L}, 392 {0xFF30E30000000000L, 0xB27EFB0000000000L}, 393 {0x8E375B8000000000L, 0xA03D948000000000L}, 394 {0xD1415C4000000000L, 0xF5357CC000000000L}, 395 {0x91A916E000000000L, 0xB6CE66E000000000L}, 396 {0xE6D2FC5000000000L, 0xD55882B000000000L}, 397 {0x9A3BA0B800000000L, 0xFBD654E800000000L}, 398 {0xAEA5D2E400000000L, 0xF0E533AC00000000L}, 399 {0xDA88B7BE00000000L, 0xAA3AAEDE00000000L}, 400 {0xBA75BB4300000000L, 0xF5A811C500000000L}, 401 {0x9B6C9A2F80000000L, 0x9603CCED80000000L}, 402 {0xFABB538840000000L, 0xE2747090C0000000L}, 403 {0x8358898EA0000000L, 0x8C698D3D20000000L}, 404 {0xDA8ABD5BF0000000L, 0xF6DF3A0AF0000000L}, 405 {0xB090C3F758000000L, 0xD3B4D3D298000000L}, 406 {0xAD9882F5BC000000L, 0x88DA4FB544000000L}, 407 {0xC3C366272A000000L, 0xDCCF2A2262000000L}, 408 {0x9BC0224A97000000L, 0xAF5D96F273000000L}, 409 {0x8643FFF621800000L, 0x8E390C6EDC800000L}, 410 {0xE45C01919BC00000L, 0xCBB34C8945C00000L}, 411 {0x80D8141BC2E00000L, 0x886AFC3912200000L}, 412 {0xF605807C26500000L, 0xA3B92D28F6300000L}, 413 {0xCE9A2CFC76280000L, 0x98400C1921280000L}, 414 {0xF61894904C040000L, 0xC8BE6DBCEC8C0000L}, 415 {0xE3A44C104D160000L, 0xCA84A59443760000L}, 416 {0xC7E84953A11B0000L, 0xD9D4F6AA02CB0000L}, 417 {0xC26CDD1C9A358000L, 0x8BE8478434328000L}, 418 {0xAE125DBEB198C000L, 0xFCC5DBFD5AAAC000L}, 419 {0x86DE52A079A6A000L, 0xC5F16BD883816000L}, 420 {0xDF82486AAFE37000L, 0xA293EC735692D000L}, 421 {0xE91ABA275C272800L, 0xD686192874E3C800L}, 422 {0x963D0960DAB3FC00L, 0xBA9DE62072621400L}, 423 {0xA2188C4E8A46CE00L, 0xD31F75BCB4977E00L}, 424 {0xC43A416020A6CB00L, 0x99F57FECA12B3900L}, 425 {0xA4F72EF82A58AE80L, 0xCECE4391B81DA380L}, 426 {0xB39F119264BC0940L, 0x80A277D20DABB9C0L}, 427 {0xFD6616C0CBFA0B20L, 0xED16E64117DC11A0L}, 428 {0xFFA8BC44327B5390L, 0xEDFB13DB3B66C210L}, 429 {0xCAE8EB99E73AB548L, 0xC86135B6EA2F0B98L}, 430 {0xBA49BADCDD19B16CL, 0x8F1944AFB18564C4L}, 431 {0xECFC86D765EABBEEL, 0x9190E1C46CC13702L}, 432 {0xE1F8D6B3195D6D97L, 0xDF70267FF5E4C979L}, 433 {0xD74307D3FD3382DBL, 0x9999B3FFDC769B48L} 434 }; 435 436 438 public static final FPGenerator std64 = make(polynomials[64][0], 64); 439 440 442 public static final FPGenerator std32 = make(polynomials[32][0], 32); 443 444 447 public static final FPGenerator std40 = make(polynomials[40][0], 40); 448 450 public static final FPGenerator std24 = make(polynomials[24][0], 24); 451 } 452 | Popular Tags |