1 //
2 // Copyright (c) 2010-2024 Antmicro
3 // Copyright (c) 2022 Pieter Agten
4 //
5 // This file is licensed under the MIT License.
6 // Full license text is available in 'licenses/MIT.txt'.
7 //
8 
9 using System;
10 using System.Collections.Generic;
11 using Antmicro.Renode.Logging;
12 
13 namespace Antmicro.Renode.Utilities
14 {
15     public class CRCEngine
16     {
CRCEngine(CRCConfig crcConfig)17         public CRCEngine(CRCConfig crcConfig)
18         {
19             this.crcConfig = crcConfig;
20             Reset();
21         }
22 
CRCEngine(uint polynomial, int crcWidth, bool reflectInput = true, bool reflectOutput = true, uint init = 0, uint xorOutput = 0)23         public CRCEngine(uint polynomial, int crcWidth, bool reflectInput = true, bool reflectOutput = true,
24             uint init = 0, uint xorOutput = 0)
25             : this(new CRCConfig(polynomial, crcWidth, reflectInput, reflectOutput, init, xorOutput))
26         {
27         }
28 
CRCEngine(CRCPolynomial polynomial, bool reflectInput = true, bool reflectOutput = true, uint init = 0, uint xorOutput = 0)29         public CRCEngine(CRCPolynomial polynomial, bool reflectInput = true, bool reflectOutput = true,
30             uint init = 0, uint xorOutput = 0)
31             : this(new CRCConfig(polynomial, reflectInput, reflectOutput, init, xorOutput))
32         {
33         }
34 
Update(IEnumerable<byte> data)35         public void Update(IEnumerable<byte> data)
36         {
37             foreach(var dataByte in data)
38             {
39                 var input = (crcConfig.ReflectInput)
40                     ? BitHelper.ReverseBits(dataByte)
41                     : (uint)dataByte;
42 
43                 crc ^= input << 24;
44                 var table_index = (byte)(crc >> 24);
45                 crc = (crc << 8) ^ Table[table_index];
46             }
47         }
48 
Reset()49         public void Reset()
50         {
51             RawValue = crcConfig.Init;
52         }
53 
Calculate(IEnumerable<byte> data)54         public uint Calculate(IEnumerable<byte> data)
55         {
56             Reset();
57             Update(data);
58             return Value;
59         }
60 
61         public CRCConfig Config => crcConfig;
62 
63         // This is the value without output reflection and output xoring
64         public uint RawValue
65         {
66             get => crc >> (CRCConfig.MaxCRCWidth - crcConfig.Width);
67             set
68             {
69                 crc = value << (CRCConfig.MaxCRCWidth - crcConfig.Width);
70             }
71         }
72 
73         public uint Value
74         {
75             get
76             {
77                 var crcAfterReflecting = (crcConfig.ReflectOutput)
78                     ? BitHelper.ReverseBits(crc)
79                     : RawValue;
80 
81                 return crcAfterReflecting ^ crcConfig.XorOutput;
82             }
83         }
84 
GenerateLookupTable(CRCPolynomial crcPolynomial)85         private static uint[] GenerateLookupTable(CRCPolynomial crcPolynomial)
86         {
87             if(tablesCache.ContainsKey(crcPolynomial) && tablesCache[crcPolynomial] != null)
88             {
89                 return tablesCache[crcPolynomial];
90             }
91 
92             var table = new uint[CRCTableSize];
93             var shiftedPoly = crcPolynomial.Polynomial << (CRCConfig.MaxCRCWidth - crcPolynomial.Width);
94 
95             for(var dividend = 0u; dividend < table.Length; dividend++)
96             {
97                 var value = dividend << 24;
98                 for(var bit = 0; bit < 8; bit++)
99                 {
100                     if((value & 0x80000000) != 0)
101                     {
102                         value <<= 1;
103                         value ^= shiftedPoly;
104                     }
105                     else
106                     {
107                         value <<= 1;
108                     }
109                 }
110                 table[dividend] = value;
111             }
112 
113             if(tablesCache.ContainsKey(crcPolynomial))
114             {
115                 tablesCache[crcPolynomial] = table;
116             }
117 
118             return table;
119         }
120 
121         private static readonly Dictionary<CRCPolynomial, uint[]> tablesCache = new Dictionary<CRCPolynomial, uint[]>()
122         {
123             { CRCPolynomial.CRC32, null },
124             { CRCPolynomial.CRC32C, null },
125             { CRCPolynomial.CRC16, null },
126             { CRCPolynomial.CRC16_CCITT, null },
127             { CRCPolynomial.CRC8_CCITT, null },
128             { CRCPolynomial.CRC7, null }
129         };
130 
131         private uint[] Table
132         {
133             get
134             {
135                 if(table == null)
136                 {
137                     table = GenerateLookupTable(crcConfig.CRCPolynomial);
138                 }
139                 return table;
140             }
141         }
142 
143         private uint crc;
144         private uint[] table;
145 
146         private readonly CRCConfig crcConfig;
147 
148         private const int CRCTableSize = 256;
149     }
150 
151     public struct CRCConfig
152     {
CRCConfigAntmicro.Renode.Utilities.CRCConfig153         public CRCConfig(uint polynomial, int width, bool reflectInput, bool reflectOutput,
154             uint init, uint xorOutput)
155             : this(new CRCPolynomial(polynomial, width), reflectInput, reflectOutput, init, xorOutput)
156         {
157         }
158 
CRCConfigAntmicro.Renode.Utilities.CRCConfig159         public CRCConfig(CRCPolynomial crcPolynomial, bool reflectInput, bool reflectOutput,
160             uint init, uint xorOutput)
161         {
162             CRCPolynomial = crcPolynomial;
163             ReflectInput = reflectInput;
164             ReflectOutput = reflectOutput;
165             BitHelper.ClearBits(ref init, crcPolynomial.Width, MaxCRCWidth - crcPolynomial.Width);
166             Init = init;
167             BitHelper.ClearBits(ref xorOutput, crcPolynomial.Width, MaxCRCWidth - crcPolynomial.Width);
168             XorOutput = xorOutput;
169         }
170 
171         public CRCPolynomial CRCPolynomial { get; }
172         public bool ReflectInput { get; }
173         public bool ReflectOutput { get; }
174         public uint Init { get; }
175         public uint XorOutput { get; }
176 
177         public uint Polynomial => CRCPolynomial.Polynomial;
178 
179         public int Width => CRCPolynomial.Width;
180 
181         public const int MaxCRCWidth = 32;
182     }
183 
184     public struct CRCPolynomial
185     {
CRCPolynomialAntmicro.Renode.Utilities.CRCPolynomial186         public CRCPolynomial(uint polynomial, int width)
187         {
188             if(width < 1 || width > 32)
189             {
190                 throw new ArgumentOutOfRangeException($"CRCConfig: {width} is incorrect width value");
191             }
192             if(BitHelper.GetMostSignificantSetBitIndex(polynomial) + 1 > width)
193             {
194                 throw new ArgumentException($"CRCConfig: width ({width}) is too small for given polynomial 0x{polynomial:X}.");
195             }
196 
197             Polynomial = polynomial;
198             Width = width;
199         }
200 
201         public uint Polynomial { get; }
202         public int Width { get; }
203 
204         public int WidthInBytes
205         {
206             get
207             {
208                 return Width % 8 == 0
209                     ? Width / 8
210                     : Width / 8 + 1;
211             }
212         }
213 
214         public static readonly CRCPolynomial CRC32 = new CRCPolynomial(0x04C11DB7, 32);
215         public static readonly CRCPolynomial CRC32C = new CRCPolynomial(0x1EDC6F41, 32);
216         public static readonly CRCPolynomial CRC16 = new CRCPolynomial(0x8005, 16);
217         public static readonly CRCPolynomial CRC16_CCITT = new CRCPolynomial(0x1021, 16);
218         public static readonly CRCPolynomial CRC8_CCITT = new CRCPolynomial(0x07, 8);
219         public static readonly CRCPolynomial CRC7 = new CRCPolynomial(0x09, 7);
220     }
221 }
222