Crc64 LSB based reverse implementation

Question

I have tried to implement LSB based reversal function. The code is in C#. There's a bug in reversal of the checksum. The function can only reverse the Crc64 checksum when it was computed with only 8 bytes original data. When I try to reverse the checksum through FixChecksum method, the middle 6 bytes are reversed, but the first & the last byte are reversed corrupted. Please inform what is wrong, what's needed to be implemented or fixed. I will appreciate any solution.

[UPDATED]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using MYC;
using primaryMethodsCS_2;
using System.Globalization;
using UnitsFramework.Numerics;
using UnitsFramework;

namespace MYC
{
    public class Crc64_LSB_Reverse
    {
        public const UInt64 POLY64REV = 0xD800000000000000; //0xffffffffffffff00;

        public static ulong TOPBIT_MASK = 0x8000000000000000;
        public static ulong LOWBIT_MASK = 0x0000000000000001;

        public const ulong startxor = 0; //0xffffffffffffffff;
        public const ulong FinalXor = 0; // 0xffffffffffffffff;

        public UInt64[] CRCTable;
        public UInt64[] revCRCTable;
        public UInt64 crc = 0;

        public Crc64_LSB_Reverse(UInt64 POLY = POLY64REV)
        {
            List<ulong> listforward = new List<ulong>();
            List<ulong> listreverse = new List<ulong>();

            for (int i = 0; i <= 255; i++)
            {
                List<ulong> forward = generateCrcTableConstants(new List<ulong>() { (UInt64)i }, POLY);
                List<ulong> reverse = generateRevCrcTableConstants(new List<ulong>() { (UInt64)i }, POLY);

                listforward.AddRange(forward);
                listreverse.AddRange(reverse);
            }

            this.CRCTable = listforward.ToArray();
            this.revCRCTable = listreverse.ToArray();

            return;
        }

        public static List<UInt64> generateCrcTableConstants(List<UInt64> initialValues, UInt64 POLY)
        {
            List<UInt64> list = new List<ulong>();

            for (int thisValue = 0; thisValue < initialValues.Count; thisValue++)
            {
                UInt64 currentValue = initialValues[thisValue];
                UInt64 initialValue = currentValue;
                currentValue <<= 56; // is valid for MSB forward table creation

                // MSB based forward table implementation.
                for (byte bit = 0; bit < 8; bit++)
                {

                    if ((currentValue & TOPBIT_MASK) != 0)
                    {
                        //currentValue <<= 1;
                        //currentValue ^= CrcFramework.Reflect64(POLY);
                        currentValue = (currentValue << 1) ^ ((0 - (currentValue >> 63)) & POLY); // fwd
                    }
                    else
                    {
                        currentValue <<= 1;
                    }
                }
                list.Add(currentValue);
            }
            return list;
        }

        public static List<UInt64> generateRevCrcTableConstants(List<UInt64> initialValues, UInt64 POLY)
        {
            List<UInt64> list = new List<ulong>();

            for (int thisValue = 0; thisValue < initialValues.Count; thisValue++)
            {
                UInt64 initialValue = initialValues[thisValue];
                UInt64 currentValue = initialValues[thisValue];

                // LSB based reverse table implementation for MSB based forward table function.
                for (byte bit = 0; bit < 8; bit++)
                {
                    if ((currentValue & LOWBIT_MASK) != 0)
                    {
                        //currentValue ^= POLY; // CrcFramework.Reflect64(POLY); //POLY;
                        currentValue = (currentValue >> 1) ^ ((0 - (currentValue & 1)) & POLY); // rvs
                        //currentValue >>= 1;
                        //currentValue |= 1; // TOPBIT_MASK;
                    }
                    else
                    {
                        currentValue >>= 1;
                    }
                }
                list.Add(currentValue);
            }
            return list;
        }

        public ulong Compute_LSB(byte[] bytes, bool reset = true)
        {
            if (reset) this.crc = startxor;

            foreach (byte b in bytes)
            {
                byte curByte = b;

                /* update the LSB of crc value with next input byte */
                crc = (ulong)(crc ^ (ulong)(curByte));
                /* this byte value is the index into the lookup table */
                byte pos = (byte)(crc & 0xFF); // tushar: original 12-September-2019-1: & 0xFF);
                /* shift out this index */
                crc = (ulong)(crc >> 8);
                /* XOR-in remainder from lookup table using the calculated index */
                crc = (ulong)(crc ^ (ulong)CRCTable[pos]);

                /* shorter:
                byte pos = (byte)((crc ^ curByte) & 0xFF);
                crc = (ulong)((crc >> 8) ^ (ulong)(crcTable[pos]));
                */
            }
            return (ulong)(crc ^ FinalXor);
        }

        public ulong Compute_MSB(byte[] bytes, bool reset = true)
        {
            if (reset) this.crc = startxor;

            foreach (byte b in bytes)
            {
                byte curByte = b;

                /* update the MSB of crc value with next input byte */
                crc = (ulong)(crc ^ (ulong)((ulong)curByte << 56));
                /* this MSB byte value is the index into the lookup table */
                byte pos = (byte)(crc >> 56);
                /* shift out this index */
                crc = (ulong)(crc << 8);
                /* XOR-in remainder from lookup table using the calculated index */
                crc = (ulong)(crc ^ (ulong)CRCTable[pos]);

                /* shorter:
                byte pos = (byte)((crc ^ (curByte << 56)) >> 56);
                crc = (uint)((crc << 8) ^ (ulong)(crcTable[pos]));
                */
            }
            return (ulong)(crc ^ FinalXor);
        }

        public UInt64 FixChecksum(byte[] bytes, Int64 length, Int64 fixpos, UInt64 wantcrc)
        {
            if (fixpos + 8 > length) return 0;

            UInt64 crc = startxor;
            for (Int64 i = 0; i < fixpos; i++)
            {
                crc = (crc >> 8) ^ CRCTable[(crc ^ bytes[i]) & 0xff];
            }

            Array.Copy(BitConverter.GetBytes(crc), 0, bytes, fixpos, 8);

            List<UInt64> list = new List<UInt64>();

            crc = wantcrc ^ startxor;
            for (Int64 i = length - 1; i >= fixpos; i--)
            {

                UInt64 param0 = (UInt64)(crc >> 56); 
                list.Add(param0);
                crc = (crc << 8) ^ revCRCTable[param0] ^ bytes[i]; //
            }

            Array.Copy(BitConverter.GetBytes(crc), 0, bytes, fixpos, 8);
            return crc;
        }

    }
}

Answer 1

The solution to this problem involves reverse cycling a CRC.

If using tables, for CRC generation (forward cycling), a left shifting CRC uses the left byte of the CRC to index a table, and a right shifting CRC uses the right byte of the CRC to index a table. For CRC reverse cycling, a left shifting CRC uses the right byte of the CRC to index a table, and a right shifting CRC uses the left byte of the CRC to index a table.

Example code below for both left shifting and right shifting CRCs. Two additional tables are used for reverse cycling CRCs. The CRC functions take in a data length parameter, in case the buffer has additional space to store the CRC after generating it.

To simplify the reverse cycling functions, a CRC is generated and xor'ed with the wanted CRC, that can be used with an imaginary buffer of zeroes, to generate the 8 bytes of data needed to produce the xor'ed CRC. The 8 bytes of data are then xor'ed to the original buffer. The xor's cancel out the CRC initial and xor out values, so the reverse cycling functions don't have to take those values into account.

Note that the CRC bytes can go anywhere in a message (although they are usually at the end of a message). For example a 24 byte message consisting of 8 bytes of data, 8 bytes of CRC, 8 bytes of data, which can be created using crc64fw(0ul, bfr, 24, 8); or crc64rw(0ul, bfr, 24, 8);.

namespace crc64
{
    public class crc64
    {
        public const ulong poly64f = 0x000000000000001bul;
        public const ulong poly64r = 0xd800000000000000ul;
        public const ulong crcin   = 0x0000000000000000ul; // initial value
        public const ulong xorot   = 0x0000000000000000ul; // xorout

        public static ulong[] crctblf;          // fwd tbl
        public static ulong[] crctblg;          // fwd tbl reverse cycle
        public static ulong[] crctblr;          // ref tbl
        public static ulong[] crctbls;          // ref tbl reverse cycle

        // generate tables
        public static void gentbls()
        {
            ulong crc;
            byte b;
            b = 0;
            do
            {
                crc = ((ulong)b)<<56;
                for(int i = 0; i < 8; i++)
                    crc = (crc<<1)^((0-(crc>>63))&poly64f);
                crctblf[b] = crc;
                b++;
            }while (b != 0);
            do
            {
                crc = ((ulong)b) << 0;
                for (int i = 0; i < 8; i++)
                    crc = (crc<<63)^((crc^((0-(crc&1))&poly64f))>>1);
                crctblg[b] = crc;
                b++;
            } while (b != 0);
            do
            {
                crc = ((ulong)b)<<0;
                for(int i = 0; i < 8; i++)
                    crc = (crc>>1)^((0-(crc&1))&poly64r);
                crctblr[b] = crc;
                b++;
            }while (b != 0);
            do
            {
                crc = ((ulong)b) << 56;
                for (int i = 0; i < 8; i++)
                    crc = (crc>>63)^((crc^((0-(crc>>63))&poly64r))<<1);
                crctbls[b] = crc;
                b++;
            } while (b != 0);
        }

        // generate forward crc
        public static ulong crc64f(byte[] bfr, int len)
        {
            ulong crc = crcin;
            for(int i = 0; i < len; i++)
                crc = (crc<<8)^(crctblf[(crc>>56)^bfr[i]]);
            return (crc^xorot);
        }

        // append forward crc
        public static void crc64fa(ulong crc, byte[] bfr, int pos)
        {
            bfr[pos+0] = (byte)(crc>>56);
            bfr[pos+1] = (byte)(crc>>48);
            bfr[pos+2] = (byte)(crc>>40);
            bfr[pos+3] = (byte)(crc>>32);
            bfr[pos+4] = (byte)(crc>>24);
            bfr[pos+5] = (byte)(crc>>16);
            bfr[pos+6] = (byte)(crc>> 8);
            bfr[pos+7] = (byte)(crc>> 0);
        }

        // "fix" bfr to generate wanted forward crc
        public static void crc64fw(ulong crc, byte[] bfr, int len, int pos)
        {
            crc ^= crc64f(bfr, len);
            for(int i = pos; i < len; i++)
                crc = (crc>>8)^(crctblg[crc&0xff]);
            bfr[pos+0] ^= (byte)(crc>>56);
            bfr[pos+1] ^= (byte)(crc>>48);
            bfr[pos+2] ^= (byte)(crc>>40);
            bfr[pos+3] ^= (byte)(crc>>32);
            bfr[pos+4] ^= (byte)(crc>>24);
            bfr[pos+5] ^= (byte)(crc>>16);
            bfr[pos+6] ^= (byte)(crc>> 8);
            bfr[pos+7] ^= (byte)(crc>> 0);
        }

        // generate reflected crc
        public static ulong crc64r(byte[] bfr, int len)
        {
            ulong crc = crcin;
            for(int i = 0; i < len; i++)
                crc = (crc>>8)^(crctblr[(crc&0xff)^bfr[i]]);
            return (crc^xorot);
        }

        // append reflected crc
        public static void crc64ra(ulong crc, byte[] bfr, int pos)
        {
            bfr[pos+0] = (byte)(crc>> 0);
            bfr[pos+1] = (byte)(crc>> 8);
            bfr[pos+2] = (byte)(crc>>16);
            bfr[pos+3] = (byte)(crc>>24);
            bfr[pos+4] = (byte)(crc>>32);
            bfr[pos+5] = (byte)(crc>>40);
            bfr[pos+6] = (byte)(crc>>48);
            bfr[pos+7] = (byte)(crc>>56);
        }

        // "fix" bfr to generate wanted reflected crc
        public static void crc64rw(ulong crc, byte[] bfr, int len, int pos)
        {
            crc ^= crc64r(bfr, len);
            for (int i = pos; i < len; i++)
                crc = (crc<<8)^(crctbls[crc>>56]);
            bfr[pos+0] ^= (byte)(crc>> 0);
            bfr[pos+1] ^= (byte)(crc>> 8);
            bfr[pos+2] ^= (byte)(crc>>16);
            bfr[pos+3] ^= (byte)(crc>>24);
            bfr[pos+4] ^= (byte)(crc>>32);
            bfr[pos+5] ^= (byte)(crc>>40);
            bfr[pos+6] ^= (byte)(crc>>48);
            bfr[pos+7] ^= (byte)(crc>>56);
        }

        static void Main(string[] args)
        {
            crctblf = new ulong[256];
            crctblg = new ulong[256];
            crctblr = new ulong[256];
            crctbls = new ulong[256];
            byte[] bfr = {0x30,0x31,0x32,0x33,0x34,0x35,0x36,0x37,   // data (16 bytes)
                          0x38,0x39,0x61,0x62,0x63,0x64,0x65,0x66,
                          0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};  // space for crc
            ulong crcf, crcr, crcw, crcg, crcs;
            int dl = bfr.Length-8;          // length of data
            int bl = bfr.Length;            // length of bfr
            gentbls();
            crcf = crc64f(bfr, dl);         // forward crc
            crc64fa(crcf, bfr, dl);         // append crc
            crcw = crc64f(bfr, bl);         // crcw == 0
            crcr = crc64r(bfr, dl);         // reflected crc
            crc64ra(crcr, bfr, dl);         // append crc
            crcw = crc64r(bfr, bl);         // crcw == 0
            Console.WriteLine(crcf.ToString("x16") + " " + crcr.ToString("x16"));
            crcw = 0x0001020304050607ul;    // wanted crc
            crc64fw(crcw, bfr, dl, 8);      // "fix" for forward
            crcg = crc64f(bfr, dl);         // crcg == crcw
            crc64fw(crcf, bfr, dl, 8);      // undo "fix" for forward (restore bfr)
            crc64rw(crcw, bfr, dl, 8);      // "fix" for reflected
            crcs = crc64r(bfr, dl);         // crcs == crcw
            Console.WriteLine(crcg.ToString("x16") + " " + crcs.ToString("x16"));
        }
    }
}