diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/gf.go | 128 |
1 files changed, 128 insertions, 0 deletions
diff --git a/lib/gf.go b/lib/gf.go new file mode 100644 index 0000000..52715ce --- /dev/null +++ b/lib/gf.go @@ -0,0 +1,128 @@ +// Copyright © 2020 rsiddharth <s@ricketyspace.net> +// SPDX-License-Identifier: ISC + +package lib + +// GF(2^8) Multiplication +// Adapted from +// https://matthewvaneerde.wordpress.com/efficient-multiplication-and-division-in-gf2 +func GFMultiply(a, b byte) byte { + if a == 0x00 || b == 0x00 { + return 0x00 + } + + ans := logXPlusOneOf[a] + logXPlusOneOf[b] + if ans >= 255 { + ans -= 255 + } + return xPlusOneToThe[ans] +} + +var xPlusOneToThe map[byte]byte = map[byte]byte{ + 0: 0x01, 1: 0x03, 2: 0x05, 3: 0x0f, 4: 0x11, + 5: 0x33, 6: 0x55, 7: 0xff, 8: 0x1a, 9: 0x2e, + 10: 0x72, 11: 0x96, 12: 0xa1, 13: 0xf8, 14: 0x13, + 15: 0x35, 16: 0x5f, 17: 0xe1, 18: 0x38, 19: 0x48, + 20: 0xd8, 21: 0x73, 22: 0x95, 23: 0xa4, 24: 0xf7, + 25: 0x02, 26: 0x06, 27: 0x0a, 28: 0x1e, 29: 0x22, + 30: 0x66, 31: 0xaa, 32: 0xe5, 33: 0x34, 34: 0x5c, + 35: 0xe4, 36: 0x37, 37: 0x59, 38: 0xeb, 39: 0x26, + 40: 0x6a, 41: 0xbe, 42: 0xd9, 43: 0x70, 44: 0x90, + 45: 0xab, 46: 0xe6, 47: 0x31, 48: 0x53, 49: 0xf5, + 50: 0x04, 51: 0x0c, 52: 0x14, 53: 0x3c, 54: 0x44, + 55: 0xcc, 56: 0x4f, 57: 0xd1, 58: 0x68, 59: 0xb8, + 60: 0xd3, 61: 0x6e, 62: 0xb2, 63: 0xcd, 64: 0x4c, + 65: 0xd4, 66: 0x67, 67: 0xa9, 68: 0xe0, 69: 0x3b, + 70: 0x4d, 71: 0xd7, 72: 0x62, 73: 0xa6, 74: 0xf1, + 75: 0x08, 76: 0x18, 77: 0x28, 78: 0x78, 79: 0x88, + 80: 0x83, 81: 0x9e, 82: 0xb9, 83: 0xd0, 84: 0x6b, + 85: 0xbd, 86: 0xdc, 87: 0x7f, 88: 0x81, 89: 0x98, + 90: 0xb3, 91: 0xce, 92: 0x49, 93: 0xdb, 94: 0x76, + 95: 0x9a, 96: 0xb5, 97: 0xc4, 98: 0x57, 99: 0xf9, + 100: 0x10, 101: 0x30, 102: 0x50, 103: 0xf0, 104: 0x0b, + 105: 0x1d, 106: 0x27, 107: 0x69, 108: 0xbb, 109: 0xd6, + 110: 0x61, 111: 0xa3, 112: 0xfe, 113: 0x19, 114: 0x2b, + 115: 0x7d, 116: 0x87, 117: 0x92, 118: 0xad, 119: 0xec, + 120: 0x2f, 121: 0x71, 122: 0x93, 123: 0xae, 124: 0xe9, + 125: 0x20, 126: 0x60, 127: 0xa0, 128: 0xfb, 129: 0x16, + 130: 0x3a, 131: 0x4e, 132: 0xd2, 133: 0x6d, 134: 0xb7, + 135: 0xc2, 136: 0x5d, 137: 0xe7, 138: 0x32, 139: 0x56, + 140: 0xfa, 141: 0x15, 142: 0x3f, 143: 0x41, 144: 0xc3, + 145: 0x5e, 146: 0xe2, 147: 0x3d, 148: 0x47, 149: 0xc9, + 150: 0x40, 151: 0xc0, 152: 0x5b, 153: 0xed, 154: 0x2c, + 155: 0x74, 156: 0x9c, 157: 0xbf, 158: 0xda, 159: 0x75, + 160: 0x9f, 161: 0xba, 162: 0xd5, 163: 0x64, 164: 0xac, + 165: 0xef, 166: 0x2a, 167: 0x7e, 168: 0x82, 169: 0x9d, + 170: 0xbc, 171: 0xdf, 172: 0x7a, 173: 0x8e, 174: 0x89, + 175: 0x80, 176: 0x9b, 177: 0xb6, 178: 0xc1, 179: 0x58, + 180: 0xe8, 181: 0x23, 182: 0x65, 183: 0xaf, 184: 0xea, + 185: 0x25, 186: 0x6f, 187: 0xb1, 188: 0xc8, 189: 0x43, + 190: 0xc5, 191: 0x54, 192: 0xfc, 193: 0x1f, 194: 0x21, + 195: 0x63, 196: 0xa5, 197: 0xf4, 198: 0x07, 199: 0x09, + 200: 0x1b, 201: 0x2d, 202: 0x77, 203: 0x99, 204: 0xb0, + 205: 0xcb, 206: 0x46, 207: 0xca, 208: 0x45, 209: 0xcf, + 210: 0x4a, 211: 0xde, 212: 0x79, 213: 0x8b, 214: 0x86, + 215: 0x91, 216: 0xa8, 217: 0xe3, 218: 0x3e, 219: 0x42, + 220: 0xc6, 221: 0x51, 222: 0xf3, 223: 0x0e, 224: 0x12, + 225: 0x36, 226: 0x5a, 227: 0xee, 228: 0x29, 229: 0x7b, + 230: 0x8d, 231: 0x8c, 232: 0x8f, 233: 0x8a, 234: 0x85, + 235: 0x94, 236: 0xa7, 237: 0xf2, 238: 0x0d, 239: 0x17, + 240: 0x39, 241: 0x4b, 242: 0xdd, 243: 0x7c, 244: 0x84, + 245: 0x97, 246: 0xa2, 247: 0xfd, 248: 0x1c, 249: 0x24, + 250: 0x6c, 251: 0xb4, 252: 0xc7, 253: 0x52, 254: 0xf6, +} + +// Inverse of xPlusOneToThe +var logXPlusOneOf map[byte]byte = map[byte]byte{ + 0x01: 0, 0x02: 25, 0x03: 1, 0x04: 50, 0x05: 2, + 0x06: 26, 0x07: 198, 0x08: 75, 0x09: 199, 0x0a: 27, + 0x0b: 104, 0x0c: 51, 0x0d: 238, 0x0e: 223, 0x0f: 3, + 0x10: 100, 0x11: 4, 0x12: 224, 0x13: 14, 0x14: 52, + 0x15: 141, 0x16: 129, 0x17: 239, 0x18: 76, 0x19: 113, + 0x1a: 8, 0x1b: 200, 0x1c: 248, 0x1d: 105, 0x1e: 28, + 0x1f: 193, 0x20: 125, 0x21: 194, 0x22: 29, 0x23: 181, + 0x24: 249, 0x25: 185, 0x26: 39, 0x27: 106, 0x28: 77, + 0x29: 228, 0x2a: 166, 0x2b: 114, 0x2c: 154, 0x2d: 201, + 0x2e: 9, 0x2f: 120, 0x30: 101, 0x31: 47, 0x32: 138, + 0x33: 5, 0x34: 33, 0x35: 15, 0x36: 225, 0x37: 36, + 0x38: 18, 0x39: 240, 0x3a: 130, 0x3b: 69, 0x3c: 53, + 0x3d: 147, 0x3e: 218, 0x3f: 142, 0x40: 150, 0x41: 143, + 0x42: 219, 0x43: 189, 0x44: 54, 0x45: 208, 0x46: 206, + 0x47: 148, 0x48: 19, 0x49: 92, 0x4a: 210, 0x4b: 241, + 0x4c: 64, 0x4d: 70, 0x4e: 131, 0x4f: 56, 0x50: 102, + 0x51: 221, 0x52: 253, 0x53: 48, 0x54: 191, 0x55: 6, + 0x56: 139, 0x57: 98, 0x58: 179, 0x59: 37, 0x5a: 226, + 0x5b: 152, 0x5c: 34, 0x5d: 136, 0x5e: 145, 0x5f: 16, + 0x60: 126, 0x61: 110, 0x62: 72, 0x63: 195, 0x64: 163, + 0x65: 182, 0x66: 30, 0x67: 66, 0x68: 58, 0x69: 107, + 0x6a: 40, 0x6b: 84, 0x6c: 250, 0x6d: 133, 0x6e: 61, + 0x6f: 186, 0x70: 43, 0x71: 121, 0x72: 10, 0x73: 21, + 0x74: 155, 0x75: 159, 0x76: 94, 0x77: 202, 0x78: 78, + 0x79: 212, 0x7a: 172, 0x7b: 229, 0x7c: 243, 0x7d: 115, + 0x7e: 167, 0x7f: 87, 0x80: 175, 0x81: 88, 0x82: 168, + 0x83: 80, 0x84: 244, 0x85: 234, 0x86: 214, 0x87: 116, + 0x88: 79, 0x89: 174, 0x8a: 233, 0x8b: 213, 0x8c: 231, + 0x8d: 230, 0x8e: 173, 0x8f: 232, 0x90: 44, 0x91: 215, + 0x92: 117, 0x93: 122, 0x94: 235, 0x95: 22, 0x96: 11, + 0x97: 245, 0x98: 89, 0x99: 203, 0x9a: 95, 0x9b: 176, + 0x9c: 156, 0x9d: 169, 0x9e: 81, 0x9f: 160, 0xa0: 127, + 0xa1: 12, 0xa2: 246, 0xa3: 111, 0xa4: 23, 0xa5: 196, + 0xa6: 73, 0xa7: 236, 0xa8: 216, 0xa9: 67, 0xaa: 31, + 0xab: 45, 0xac: 164, 0xad: 118, 0xae: 123, 0xaf: 183, + 0xb0: 204, 0xb1: 187, 0xb2: 62, 0xb3: 90, 0xb4: 251, + 0xb5: 96, 0xb6: 177, 0xb7: 134, 0xb8: 59, 0xb9: 82, + 0xba: 161, 0xbb: 108, 0xbc: 170, 0xbd: 85, 0xbe: 41, + 0xbf: 157, 0xc0: 151, 0xc1: 178, 0xc2: 135, 0xc3: 144, + 0xc4: 97, 0xc5: 190, 0xc6: 220, 0xc7: 252, 0xc8: 188, + 0xc9: 149, 0xca: 207, 0xcb: 205, 0xcc: 55, 0xcd: 63, + 0xce: 91, 0xcf: 209, 0xd0: 83, 0xd1: 57, 0xd2: 132, + 0xd3: 60, 0xd4: 65, 0xd5: 162, 0xd6: 109, 0xd7: 71, + 0xd8: 20, 0xd9: 42, 0xda: 158, 0xdb: 93, 0xdc: 86, + 0xdd: 242, 0xde: 211, 0xdf: 171, 0xe0: 68, 0xe1: 17, + 0xe2: 146, 0xe3: 217, 0xe4: 35, 0xe5: 32, 0xe6: 46, + 0xe7: 137, 0xe8: 180, 0xe9: 124, 0xea: 184, 0xeb: 38, + 0xec: 119, 0xed: 153, 0xee: 227, 0xef: 165, 0xf0: 103, + 0xf1: 74, 0xf2: 237, 0xf3: 222, 0xf4: 197, 0xf5: 49, + 0xf6: 254, 0xf7: 24, 0xf8: 13, 0xf9: 99, 0xfa: 140, + 0xfb: 128, 0xfc: 192, 0xfd: 247, 0xfe: 112, 0xff: 7, +} |