> {-# LANGUAGE CPP #-} > {-# LANGUAGE DataKinds #-} > {-# LANGUAGE FlexibleContexts #-} > {-# LANGUAGE OverloadedLists #-} > {-# LANGUAGE ScopedTypeVariables #-} > {-# LANGUAGE TypeOperators #-} > module Data.ReedSolomon.Galois.GenTables ( > expTable > , logTable > , mulTable > , mulTableLow > , mulTableHigh > ) where > > import Prelude hiding (log) > #if !MIN_VERSION_base(4, 8, 0) > import Control.Applicative ((<$>), (<*>)) #endif > import Control.Monad (when) > import Control.Monad.ST (runST) > import Data.Bits ((.&.), shiftR) > import Data.Maybe (fromJust) > import Data.Proxy > import Data.Word (Word8) > > import GHC.TypeLits > > import qualified Data.Vector as V (Vector) > import Data.Vector.Generic ((!)) > import qualified Data.Vector.Generic as V hiding (Vector) > import qualified Data.Vector.Generic.Mutable as MV > import qualified Data.Vector.Unboxed as UV > import qualified Data.Vector.Storable as SV > > import Control.Loop (numLoop) > > import qualified Data.Vector.Generic.Sized as S //+build ignore package main import ( "fmt" ) var logTable = [fieldSize]int16{ > logTable :: S.UVector FieldSize Word8 > logTable = [ > -1, 0, 1, 25, 2, 50, 26, 198, > 3, 223, 51, 238, 27, 104, 199, 75, > 4, 100, 224, 14, 52, 141, 239, 129, > 28, 193, 105, 248, 200, 8, 76, 113, > 5, 138, 101, 47, 225, 36, 15, 33, > 53, 147, 142, 218, 240, 18, 130, 69, > 29, 181, 194, 125, 106, 39, 249, 185, > 201, 154, 9, 120, 77, 228, 114, 166, > 6, 191, 139, 98, 102, 221, 48, 253, > 226, 152, 37, 179, 16, 145, 34, 136, > 54, 208, 148, 206, 143, 150, 219, 189, > 241, 210, 19, 92, 131, 56, 70, 64, > 30, 66, 182, 163, 195, 72, 126, 110, > 107, 58, 40, 84, 250, 133, 186, 61, > 202, 94, 155, 159, 10, 21, 121, 43, > 78, 212, 229, 172, 115, 243, 167, 87, > 7, 112, 192, 247, 140, 128, 99, 13, > 103, 74, 222, 237, 49, 197, 254, 24, > 227, 165, 153, 119, 38, 184, 180, 124, > 17, 68, 146, 217, 35, 32, 137, 46, > 55, 63, 209, 91, 149, 188, 207, 205, > 144, 135, 151, 178, 220, 252, 190, 97, > 242, 86, 211, 171, 20, 42, 93, 158, > 132, 60, 57, 83, 71, 109, 65, 162, > 31, 45, 67, 216, 183, 123, 164, 118, > 196, 23, 73, 236, 127, 12, 111, 246, > 108, 161, 59, 82, 41, 157, 85, 170, > 251, 96, 134, 177, 187, 204, 62, 90, > 203, 89, 95, 176, 156, 169, 160, 81, > 11, 245, 22, 235, 122, 117, 44, 215, > 79, 174, 213, 233, 230, 231, 173, 232, > 116, 214, 244, 234, 168, 80, 88, 175 > ] } const ( // The number of elements in the field. > type FieldSize = 256 > fieldSize :: Int > fieldSize = fromInteger $ natVal (Proxy :: Proxy FieldSize) // The polynomial used to generate the logarithm table. // // There are a number of polynomials that work to generate // a Galois field of 256 elements. The choice is arbitrary, // and we just use the first one. // // The possibilities are: 29, 43, 45, 77, 95, 99, 101, 105, //* 113, 135, 141, 169, 195, 207, 231, and 245. generatingPolynomial = 29 ) func main() { t := generateExpTable() fmt.Printf("var expTable = %#v\n", t) //t2 := generateMulTableSplit(t) //fmt.Printf("var mulTable = %#v\n", t2) low, high := generateMulTableHalf(t) fmt.Printf("var mulTableLow = %#v\n", low) fmt.Printf("var mulTableHigh = %#v\n", high) } /** * Generates the inverse log table. */ func generateExpTable() []byte { result := make([]byte, fieldSize*2-2) for i := 1; i < fieldSize; i++ { log := logTable[i] result[log] = byte(i) result[log+fieldSize-1] = byte(i) } return result } > expTable :: S.UVector (FieldSize * 2 - 2) Word8 > Just expTable = S.fromVector $ UV.create $ do > result <- MV.new $ fieldSize * 2 - 2 > numLoop 1 (fieldSize - 1) $ \i -> do > let log = fromIntegral $ S.index logTable (fromIntegral i :: Word8) > MV.write result log (fromIntegral i :: Word8) > MV.write result (log + fieldSize - 1) (fromIntegral i) > return result func generateMulTable(expTable []byte) []byte { result := make([]byte, 256*256) for v := range result { a := byte(v & 0xff) b := byte(v >> 8) if a == 0 || b == 0 { result[v] = 0 continue } logA := int(logTable[a]) logB := int(logTable[b]) result[v] = expTable[logA+logB] } return result } func generateMulTableSplit(expTable []byte) [256][256]byte { var result [256][256]byte for a := range result { for b := range result[a] { if a == 0 || b == 0 { result[a][b] = 0 continue } logA := int(logTable[a]) logB := int(logTable[b]) result[a][b] = expTable[logA+logB] } } return result } > mulTable :: S.Vector V.Vector FieldSize (S.UVector FieldSize Word8) > mulTable = > S.generate $ \a -> > S.generate $ \b -> > if (a == 0 || b == 0) > then 0 > else > let logA = fromIntegral $ S.index logTable (fromIntegral a :: Word8) in > let logB = fromIntegral $ S.index logTable (fromIntegral b :: Word8) in > S.toVector expTable ! (logA + logB) func generateMulTableHalf(expTable []byte) (low [256][16]byte, high [256][16]byte) { for a := range low { for b := range low { result := 0 if !(a == 0 || b == 0) { logA := int(logTable[a]) logB := int(logTable[b]) result = int(expTable[logA+logB]) } if (b & 0xf) == b { low[a][b] = byte(result) } if (b & 0xf0) == b { high[a][b>>4] = byte(result) } } } return } > mulTableLow, mulTableHigh :: S.Vector V.Vector FieldSize (S.SVector 16 Word8) > (mulTableLow, mulTableHigh) = (\(v1, v2) -> (fixup2 v1, fixup2 v2)) $ runST $ do > low :: V.Vector (SV.MVector s Word8) <- V.replicateM 256 (MV.replicate 16 0) > high :: V.Vector (SV.MVector s Word8) <- V.replicateM 256 (MV.replicate 16 0) > > numLoop 0 (V.length low - 1) $ \a -> > numLoop 0 (V.length low - 1) $ \b -> do > let result :: Int = > if not (a == 0 || b == 0) > then > let logA = fromIntegral $ S.index logTable (fromIntegral a :: Word8) in > let logB = fromIntegral $ S.index logTable (fromIntegral b :: Word8) in > fromIntegral $ S.toVector expTable ! (logA + logB) > else 0 > > when (b .&. 0xf == b) $ > MV.write (low ! a) b (fromIntegral result) > > when (b .&. 0xf0 == b) $ > MV.write (high ! a) (b `shiftR` 4) (fromIntegral result) > > (,) <$> fixup low <*> fixup high > where > fixup v = V.generateM (V.length v) $ \i -> V.unsafeFreeze (v ! i) > fixup2 = fromJust . S.fromVector . V.map (fromJust . S.fromVector)