Return to rs.c CVS log

Up to [Previous NeXT emulator] / previous_trunk / src

Annotation of previous_trunk/src/rs.c, revision 1.1

1.1     ! root        1: /*  Previous - rs.c
        !             2:  
        !             3:  This file is distributed under the GNU Public License, version 2 or at
        !             4:  your option any later version. Read the file gpl.txt for details.
        !             5: 
        !             6:  NeXT magento-optical drive controller uses cross interleaved Reed-Solomon-Codes
        !             7:  for error correction. This implementation has been written by Olivier Galibert.
        !             8:  The original code was adapted to work with Previous.
        !             9:  
        !            10:  */
        !            11: 
        !            12: #include <string.h>
        !            13: 
        !            14: #include "main.h"
        !            15: #include "rs.h"
        !            16: 
        !            17: 
        !            18: /* Reed-Solomon(36,32) in GF(2**8), generator polynomial (x-1)*(x-2)*(x-4)*(x-8)
        !            19:  GF's polynom is the usual 11d
        !            20:  */
        !            21: 
        !            22: /* Partial remainders, e.g. t_rem[i] = (i*x^4) % ((x-1)*(x-2)*(x-4)*(x-8)) */
        !            23: const Uint32 t_rem[256] = {
        !            24:        0x00000000, 0x0f367840, 0x1e6cf080, 0x115a88c0, 0x3cd8fd1d, 0x33ee855d, 0x22b40d9d, 0x2d8275dd,
        !            25:        0x78ade73a, 0x779b9f7a, 0x66c117ba, 0x69f76ffa, 0x44751a27, 0x4b436267, 0x5a19eaa7, 0x552f92e7,
        !            26:        0xf047d374, 0xff71ab34, 0xee2b23f4, 0xe11d5bb4, 0xcc9f2e69, 0xc3a95629, 0xd2f3dee9, 0xddc5a6a9,
        !            27:        0x88ea344e, 0x87dc4c0e, 0x9686c4ce, 0x99b0bc8e, 0xb432c953, 0xbb04b113, 0xaa5e39d3, 0xa5684193,
        !            28:        0xfd8ebbe8, 0xf2b8c3a8, 0xe3e24b68, 0xecd43328, 0xc15646f5, 0xce603eb5, 0xdf3ab675, 0xd00cce35,
        !            29:        0x85235cd2, 0x8a152492, 0x9b4fac52, 0x9479d412, 0xb9fba1cf, 0xb6cdd98f, 0xa797514f, 0xa8a1290f,
        !            30:        0x0dc9689c, 0x02ff10dc, 0x13a5981c, 0x1c93e05c, 0x31119581, 0x3e27edc1, 0x2f7d6501, 0x204b1d41,
        !            31:        0x75648fa6, 0x7a52f7e6, 0x6b087f26, 0x643e0766, 0x49bc72bb, 0x468a0afb, 0x57d0823b, 0x58e6fa7b,
        !            32:        0xe7016bcd, 0xe837138d, 0xf96d9b4d, 0xf65be30d, 0xdbd996d0, 0xd4efee90, 0xc5b56650, 0xca831e10,
        !            33:        0x9fac8cf7, 0x909af4b7, 0x81c07c77, 0x8ef60437, 0xa37471ea, 0xac4209aa, 0xbd18816a, 0xb22ef92a,
        !            34:        0x1746b8b9, 0x1870c0f9, 0x092a4839, 0x061c3079, 0x2b9e45a4, 0x24a83de4, 0x35f2b524, 0x3ac4cd64,
        !            35:        0x6feb5f83, 0x60dd27c3, 0x7187af03, 0x7eb1d743, 0x5333a29e, 0x5c05dade, 0x4d5f521e, 0x42692a5e,
        !            36:        0x1a8fd025, 0x15b9a865, 0x04e320a5, 0x0bd558e5, 0x26572d38, 0x29615578, 0x383bddb8, 0x370da5f8,
        !            37:        0x6222371f, 0x6d144f5f, 0x7c4ec79f, 0x7378bfdf, 0x5efaca02, 0x51ccb242, 0x40963a82, 0x4fa042c2,
        !            38:        0xeac80351, 0xe5fe7b11, 0xf4a4f3d1, 0xfb928b91, 0xd610fe4c, 0xd926860c, 0xc87c0ecc, 0xc74a768c,
        !            39:        0x9265e46b, 0x9d539c2b, 0x8c0914eb, 0x833f6cab, 0xaebd1976, 0xa18b6136, 0xb0d1e9f6, 0xbfe791b6,
        !            40:        0xd302d687, 0xdc34aec7, 0xcd6e2607, 0xc2585e47, 0xefda2b9a, 0xe0ec53da, 0xf1b6db1a, 0xfe80a35a,
        !            41:        0xabaf31bd, 0xa49949fd, 0xb5c3c13d, 0xbaf5b97d, 0x9777cca0, 0x9841b4e0, 0x891b3c20, 0x862d4460,
        !            42:        0x234505f3, 0x2c737db3, 0x3d29f573, 0x321f8d33, 0x1f9df8ee, 0x10ab80ae, 0x01f1086e, 0x0ec7702e,
        !            43:        0x5be8e2c9, 0x54de9a89, 0x45841249, 0x4ab26a09, 0x67301fd4, 0x68066794, 0x795cef54, 0x766a9714,
        !            44:        0x2e8c6d6f, 0x21ba152f, 0x30e09def, 0x3fd6e5af, 0x12549072, 0x1d62e832, 0x0c3860f2, 0x030e18b2,
        !            45:        0x56218a55, 0x5917f215, 0x484d7ad5, 0x477b0295, 0x6af97748, 0x65cf0f08, 0x749587c8, 0x7ba3ff88,
        !            46:        0xdecbbe1b, 0xd1fdc65b, 0xc0a74e9b, 0xcf9136db, 0xe2134306, 0xed253b46, 0xfc7fb386, 0xf349cbc6,
        !            47:        0xa6665921, 0xa9502161, 0xb80aa9a1, 0xb73cd1e1, 0x9abea43c, 0x9588dc7c, 0x84d254bc, 0x8be42cfc,
        !            48:        0x3403bd4a, 0x3b35c50a, 0x2a6f4dca, 0x2559358a, 0x08db4057, 0x07ed3817, 0x16b7b0d7, 0x1981c897,
        !            49:        0x4cae5a70, 0x43982230, 0x52c2aaf0, 0x5df4d2b0, 0x7076a76d, 0x7f40df2d, 0x6e1a57ed, 0x612c2fad,
        !            50:        0xc4446e3e, 0xcb72167e, 0xda289ebe, 0xd51ee6fe, 0xf89c9323, 0xf7aaeb63, 0xe6f063a3, 0xe9c61be3,
        !            51:        0xbce98904, 0xb3dff144, 0xa2857984, 0xadb301c4, 0x80317419, 0x8f070c59, 0x9e5d8499, 0x916bfcd9,
        !            52:        0xc98d06a2, 0xc6bb7ee2, 0xd7e1f622, 0xd8d78e62, 0xf555fbbf, 0xfa6383ff, 0xeb390b3f, 0xe40f737f,
        !            53:        0xb120e198, 0xbe1699d8, 0xaf4c1118, 0xa07a6958, 0x8df81c85, 0x82ce64c5, 0x9394ec05, 0x9ca29445,
        !            54:        0x39cad5d6, 0x36fcad96, 0x27a62556, 0x28905d16, 0x051228cb, 0x0a24508b, 0x1b7ed84b, 0x1448a00b,
        !            55:        0x416732ec, 0x4e514aac, 0x5f0bc26c, 0x503dba2c, 0x7dbfcff1, 0x7289b7b1, 0x63d33f71, 0x6ce54731,
        !            56: };
        !            57: 
        !            58: const Uint8 t_exp[768] = {
        !            59:        0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26,
        !            60:        0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0,
        !            61:        0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23,
        !            62:        0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1,
        !            63:        0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0,
        !            64:        0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2,
        !            65:        0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce,
        !            66:        0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc,
        !            67:        0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54,
        !            68:        0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73,
        !            69:        0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff,
        !            70:        0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41,
        !            71:        0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6,
        !            72:        0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09,
        !            73:        0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16,
        !            74:        0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01,
        !            75:        0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26, 0x4c,
        !            76:        0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0, 0x9d,
        !            77:        0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23, 0x46,
        !            78:        0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1, 0x5f,
        !            79:        0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0, 0xfd,
        !            80:        0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2, 0xd9,
        !            81:        0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce, 0x81,
        !            82:        0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc, 0x85,
        !            83:        0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54, 0xa8,
        !            84:        0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73, 0xe6,
        !            85:        0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff, 0xe3,
        !            86:        0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41, 0x82,
        !            87:        0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6, 0x51,
        !            88:        0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09, 0x12,
        !            89:        0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16, 0x2c,
        !            90:        0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01, 0x02,
        !            91:        0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26, 0x4c, 0x98,
        !            92:        0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9, 0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0, 0x9d, 0x27,
        !            93:        0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35, 0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23, 0x46, 0x8c,
        !            94:        0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0, 0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1, 0x5f, 0xbe,
        !            95:        0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc, 0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0, 0xfd, 0xe7,
        !            96:        0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f, 0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2, 0xd9, 0xaf,
        !            97:        0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce, 0x81, 0x1f,
        !            98:        0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93, 0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc, 0x85, 0x17,
        !            99:        0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9, 0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54, 0xa8, 0x4d,
        !           100:        0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa, 0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73, 0xe6, 0xd1,
        !           101:        0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e, 0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff, 0xe3, 0xdb,
        !           102:        0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4, 0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41, 0x82, 0x19,
        !           103:        0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e, 0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6, 0x51, 0xa2,
        !           104:        0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef, 0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09, 0x12, 0x24,
        !           105:        0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5, 0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16, 0x2c, 0x58,
        !           106:        0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83, 0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01, 0x02, 0x04,
        !           107: };
        !           108: 
        !           109: const Uint8 t_log[256] = {
        !           110:        0x00, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6, 0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b,
        !           111:        0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81, 0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71,
        !           112:        0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21, 0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45,
        !           113:        0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9, 0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6,
        !           114:        0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd, 0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88,
        !           115:        0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd, 0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40,
        !           116:        0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e, 0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d,
        !           117:        0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b, 0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57,
        !           118:        0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d, 0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18,
        !           119:        0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c, 0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e,
        !           120:        0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd, 0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61,
        !           121:        0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e, 0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2,
        !           122:        0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76, 0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6,
        !           123:        0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa, 0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a,
        !           124:        0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51, 0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7,
        !           125:        0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8, 0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf,
        !           126: };
        !           127: 
        !           128: static Uint32 ecc_block(const Uint8 *s, int ss)
        !           129: {
        !           130:     int i;
        !           131:     Uint32 r = (s[0] << 24) | (s[ss] << 16) | (s[2*ss] << 8) | s[3*ss];
        !           132:     
        !           133:     s += 4*ss;
        !           134:     for(i=4; i<36; i++) {
        !           135:         r = t_rem[r >> 24] ^ (r << 8);
        !           136:         if(i < 32) {
        !           137:             r ^= *s;
        !           138:             s += ss;
        !           139:         }
        !           140:     }
        !           141:     return r;
        !           142: }
        !           143: 
        !           144: static void rs_encode_string(Uint8 *sector, int off, int step)
        !           145: {
        !           146:        Uint32 ecc = ecc_block(sector+off, step);
        !           147:        sector[off+32*step] = ecc >> 24;
        !           148:        sector[off+33*step] = ecc >> 16;
        !           149:        sector[off+34*step] = ecc >> 8;
        !           150:        sector[off+35*step] = ecc;
        !           151: }
        !           152: 
        !           153: static int rs_decode_string(Uint8 *sector, int off, int step)
        !           154: {
        !           155:     int i;
        !           156:        Uint32 ecc = ecc_block(sector+off, step);
        !           157:        Uint32 ref_ecc =
        !           158:     (sector[off+32*step] << 24) |
        !           159:     (sector[off+33*step] << 16) |
        !           160:     (sector[off+34*step] << 8) |
        !           161:     sector[off+35*step];
        !           162:        if(ref_ecc == ecc)
        !           163:                return 0;
        !           164:     
        !           165:        // Syndrome polynomial
        !           166:        // syn[i] = value of the codebook polynom at 2**(i-1)
        !           167:        Uint8 syn[5];
        !           168:        memset(syn, 0, 5);
        !           169:        syn[0] = 1;
        !           170:        for(i=0; i<36; i++) {
        !           171:                Uint8 v = sector[off+step*(35-i)];
        !           172:                if(v) {
        !           173:                        syn[1] ^= v;
        !           174:                        int lv = t_log[v];
        !           175:                        syn[2] ^= t_exp[lv+i];
        !           176:                        syn[3] ^= t_exp[lv+2*i];
        !           177:                        syn[4] ^= t_exp[lv+3*i];
        !           178:                }
        !           179:        }
        !           180:     
        !           181:        // Berlekamp-Massey
        !           182:     
        !           183:        Uint8 sigma[5];
        !           184:        Uint8 omega[5];
        !           185:        Uint8 tau[5];
        !           186:        Uint8 gamma[5];
        !           187:        int d;
        !           188:        int b;
        !           189:     
        !           190:        memset(sigma, 0, 5);
        !           191:        memset(omega, 0, 5);
        !           192:        memset(tau, 0, 5);
        !           193:        memset(gamma, 0, 5);
        !           194:        sigma[0] = 1;
        !           195:        omega[0] = 1;
        !           196:        tau[0] = 1;
        !           197:        d = 0;
        !           198:        b = 0;
        !           199:     
        !           200:     int l;
        !           201:        for(l=1; l<5; l++) {
        !           202:                // 1- Determine the l-order coefficient syn*sigma
        !           203:                Uint8 delta = 0;
        !           204:                for(i=0; i<=l; i++)
        !           205:                        if(sigma[i] && syn[l-i])
        !           206:                                delta ^= t_exp[t_log[sigma[i]] + t_log[syn[l-i]]];
        !           207:         
        !           208:                // 2- Select update method a/b
        !           209:                int limit = (l+1)/2;
        !           210:                int exact = l & 1;
        !           211:                if(!delta || d > limit || (d == limit && exact && !b)) {
        !           212:                        // 2.1- Method a
        !           213:                        // b and d unchanged
        !           214:                        // tau and gamma multiplied by x
        !           215:                        // sigma = sigma - delta * tau
        !           216:                        // omega = omega - delta * gamma
        !           217:             
        !           218:                        for(i=0; i<l; i++) {
        !           219:                                tau[l-i] = tau[l-i-1];
        !           220:                                gamma[l-i] = gamma[l-i-1];
        !           221:                        }
        !           222:                        tau[0] = gamma[0] = 0;
        !           223:             
        !           224:                        if(delta) {
        !           225:                                Uint8 ldelta = t_log[delta];
        !           226:                                for(i=1; i<=l; i++) {
        !           227:                                        if(tau[i])
        !           228:                                                sigma[i] ^= t_exp[t_log[tau  [i]] + ldelta];
        !           229:                                        if(gamma[i])
        !           230:                                                omega[i] ^= t_exp[t_log[gamma[i]] + ldelta];
        !           231:                                }
        !           232:                        }
        !           233:                } else {
        !           234:                        // 2.2- Method b
        !           235:                        d = l-d;
        !           236:                        b = !b;
        !           237:                        // tau(n+1)   = sigma(n) / delta
        !           238:                        // gamma(n+1) = omega(n) / delta
        !           239:                        // sigma(n+1) = sigma(n) - delta*x*tau(n)
        !           240:                        // omega(n+1) = omega(n) - delta*x*gamma(n)
        !           241:                        Uint8 ldelta = t_log[delta];
        !           242:                        Uint8 ildelta = ldelta ^ 255;
        !           243:                        for(i=l; i>0; i--) {
        !           244:                                if(tau[i-1])
        !           245:                                        sigma[i]   = sigma[i] ^ t_exp[t_log[tau  [i-1]] + ldelta];
        !           246:                 
        !           247:                                if(gamma[i-1])
        !           248:                                        omega[i]   = omega[i] ^ t_exp[t_log[gamma[i-1]] + ldelta];
        !           249:                 
        !           250:                                if(sigma[i-1])
        !           251:                                        tau[i-1]   = t_exp[t_log[sigma[i-1]] + ildelta];
        !           252:                                else
        !           253:                                        tau[i-1]   = 0x00;
        !           254:                 
        !           255:                                if(omega[i-1])
        !           256:                                        gamma[i-1] = t_exp[t_log[omega[i-1]] + ildelta];
        !           257:                                else
        !           258:                                        gamma[i-1]   = 0x00;
        !           259:                        }
        !           260:                }
        !           261:        }
        !           262:     
        !           263:        // Find the roots of sigma to get the error positions (they're the inverses of 2**position)
        !           264:        // Compute the error(s)
        !           265:     
        !           266:        if(sigma[3] || sigma[4]) {
        !           267:                // Should not happen
        !           268:                return -1;
        !           269:        }
        !           270:     
        !           271:        if(sigma[2] && sigma[0]) {
        !           272:                int epos1, epos2;
        !           273:                Uint8 ls1 = t_log[sigma[1]];
        !           274:                Uint8 ls2 = t_log[sigma[2]];
        !           275:                for(epos1 = 0; epos1 < 256; epos1++) {
        !           276:                        Uint8 res = sigma[0];
        !           277:                        if(sigma[1])
        !           278:                                res ^= t_exp[255-epos1+ls1];
        !           279:                        res ^= t_exp[2*(255-epos1)+ls2];
        !           280:                        if(!res)
        !           281:                                break;
        !           282:                }
        !           283:                if(epos1 > 35)
        !           284:                        return -1;
        !           285:         
        !           286:                // sigma = c.(x-1/r1)(x-1/r2) = c.x*x - c*x*(1/r1+1/r2) + c/(r1*r2)
        !           287:         
        !           288:                // s0 = s2/(r1*r2) -> r1*r2*s0 = s2 -> r1 = s2 / (r1*s0)
        !           289:                // -> r2 = sigma[2]/(r1*sigma[0])
        !           290:                epos2 = ls2 - epos1 - t_log[sigma[0]];
        !           291:                if(epos2 < 0)
        !           292:                        epos2 += 255;
        !           293:                if(epos2 > 35)
        !           294:                        return -1;
        !           295:         
        !           296:                Uint8 err1 = omega[0];
        !           297:                if(omega[1])
        !           298:                        err1 ^= t_exp[t_log[omega[1]] + 255 - epos1];
        !           299:                if(omega[2])
        !           300:                        err1 ^= t_exp[t_log[omega[2]] + 2*(255 - epos1)];
        !           301:                err1 = t_log[err1] + epos1;
        !           302:                Uint8 div = t_log[1 ^ t_exp[255 + epos2 - epos1]];
        !           303:                err1 = t_exp[255 + err1 - div];
        !           304:         
        !           305:                Uint8 err2 = omega[0];
        !           306:                if(omega[1])
        !           307:                        err2 ^= t_exp[t_log[omega[1]] + 255 - epos2];
        !           308:                if(omega[2])
        !           309:                        err2 ^= t_exp[t_log[omega[2]] + 2*(255 - epos2)];
        !           310:                err2 = t_log[err2] + epos2;
        !           311:                div = t_log[1 ^ t_exp[255 + epos1 - epos2]];
        !           312:                err2 = t_exp[255 + err2 - div];
        !           313:         
        !           314:                sector[off + step*(35-epos1)] ^= err1;
        !           315:                sector[off + step*(35-epos2)] ^= err2;
        !           316:                return 2;
        !           317:         
        !           318:        } else if(sigma[1] && sigma[0]) {
        !           319:                // sigma = c.(x-1/r1) -> r1=sigma[1]/sigma[0]
        !           320:                int epos = t_log[sigma[1]] - t_log[sigma[0]];
        !           321:         
        !           322:                if(epos > 35)
        !           323:                        return -1;
        !           324:         
        !           325:                Uint8 err = sigma[1]^omega[1];
        !           326:                sector[off + step*(35-epos)] ^= err;
        !           327:                return 1;
        !           328:         
        !           329:        } else {
        !           330:                // Should not happen
        !           331:                return -1;
        !           332:        }
        !           333: }
        !           334: 
        !           335: void rs_encode(Uint8 *sector)
        !           336: {
        !           337:     int i;
        !           338:     /* Create encoded sector structure */
        !           339:        for(i=31; i>0; i--)
        !           340:                memmove(sector+36*i, sector+32*i, 32);
        !           341:     /* Encode columns */
        !           342:        for(i=0; i<32; i++)
        !           343:                rs_encode_string(sector, i, 36);
        !           344:     /* Encode rows */
        !           345:        for(i=0; i<36; i++)
        !           346:                rs_encode_string(sector, 36*i, 1);
        !           347: }
        !           348: 
        !           349: int rs_decode(Uint8 *sector)
        !           350: {
        !           351:     int i,e;
        !           352:        int ecount = 0;
        !           353:     /* Decode rows */
        !           354:     for(i=0; i<36; i++) {
        !           355:         e = rs_decode_string(sector, 36*i, 1);
        !           356:         if(e!=-1) {
        !           357:             ecount += e;
        !           358:         }
        !           359:     }
        !           360:     /* Decode columns */
        !           361:     for(i=0; i<32; i++) {
        !           362:         e = rs_decode_string(sector, i, 36);
        !           363:         if(e==-1) {
        !           364:             return -1; /* Uncorrectable */
        !           365:         } else {
        !           366:             ecount += e;
        !           367:         }
        !           368:     }
        !           369:     /* Build decoded sector structure */
        !           370:        for(i=1; i<32; i++)
        !           371:                memmove(sector+i*32, sector+i*36, 32);
        !           372:     
        !           373:     return ecount;
        !           374: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.