galois-field.js 1.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869
  1. const EXP_TABLE = new Uint8Array(512)
  2. const LOG_TABLE = new Uint8Array(256)
  3. /**
  4. * Precompute the log and anti-log tables for faster computation later
  5. *
  6. * For each possible value in the galois field 2^8, we will pre-compute
  7. * the logarithm and anti-logarithm (exponential) of this value
  8. *
  9. * ref {@link https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#Introduction_to_mathematical_fields}
  10. */
  11. ;(function initTables () {
  12. let x = 1
  13. for (let i = 0; i < 255; i++) {
  14. EXP_TABLE[i] = x
  15. LOG_TABLE[x] = i
  16. x <<= 1 // multiply by 2
  17. // The QR code specification says to use byte-wise modulo 100011101 arithmetic.
  18. // This means that when a number is 256 or larger, it should be XORed with 0x11D.
  19. if (x & 0x100) { // similar to x >= 256, but a lot faster (because 0x100 == 256)
  20. x ^= 0x11D
  21. }
  22. }
  23. // Optimization: double the size of the anti-log table so that we don't need to mod 255 to
  24. // stay inside the bounds (because we will mainly use this table for the multiplication of
  25. // two GF numbers, no more).
  26. // @see {@link mul}
  27. for (let i = 255; i < 512; i++) {
  28. EXP_TABLE[i] = EXP_TABLE[i - 255]
  29. }
  30. }())
  31. /**
  32. * Returns log value of n inside Galois Field
  33. *
  34. * @param {Number} n
  35. * @return {Number}
  36. */
  37. exports.log = function log (n) {
  38. if (n < 1) throw new Error('log(' + n + ')')
  39. return LOG_TABLE[n]
  40. }
  41. /**
  42. * Returns anti-log value of n inside Galois Field
  43. *
  44. * @param {Number} n
  45. * @return {Number}
  46. */
  47. exports.exp = function exp (n) {
  48. return EXP_TABLE[n]
  49. }
  50. /**
  51. * Multiplies two number inside Galois Field
  52. *
  53. * @param {Number} x
  54. * @param {Number} y
  55. * @return {Number}
  56. */
  57. exports.mul = function mul (x, y) {
  58. if (x === 0 || y === 0) return 0
  59. // should be EXP_TABLE[(LOG_TABLE[x] + LOG_TABLE[y]) % 255] if EXP_TABLE wasn't oversized
  60. // @see {@link initTables}
  61. return EXP_TABLE[LOG_TABLE[x] + LOG_TABLE[y]]
  62. }