Page 1 of 1

How to calculate the CRC32 of 1 by hand?

Posted: 16 Mar 2019, 15:54
by afe
How to calculate the CRC32 of 1 by hand?


100000000000000000000000000000000
100000100110000010001110110110111
----------------------------------------------------
100110000010001110110110111


Why the result is not 0xA505DF1B?

Re: How to calculate the CRC32 of 1 by hand?

Posted: 16 Mar 2019, 20:15
by IMEime

Re: How to calculate the CRC32 of 1 by hand?

Posted: 16 Mar 2019, 20:31
by jeeswg
There's also this:
CRC-32 hash tutorial - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=7&t=35671

Re: How to calculate the CRC32 of 1 by hand?

Posted: 16 Mar 2019, 20:42
by IMEime
Ho.. really good one
-I just SIMPLE Googled, and pick the several ones from the first of the page

Re: How to calculate the CRC32 of 1 by hand?

Posted: 17 Mar 2019, 00:56
by afe
jeeswg wrote:
16 Mar 2019, 20:31
There's also this:
CRC-32 hash tutorial - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=7&t=35671
I have already read this post from you, but I still don't understand why to do this?.
Are you using ISO/IEC/IEEE 802-3 CRC32? Where is the document for ISO/IEC/IEEE 802-3 CRC32?

Re: How to calculate the CRC32 of 1 by hand?

Posted: 17 Mar 2019, 05:16
by jeeswg
- You can test here:
Online CRC-8 CRC-16 CRC-32 Calculator
https://crccalc.com/
- For the 1-byte ASCII character 1, which is Chr(49) = Chr(0x31), which is the 1-byte hex 0x31 = 0b00110001 you get CRC-32 hash 0x83DCEFB7.
- For the 1-byte hex 0x01 = 0b00000001, you get CRC-32 hash 0xA505DF1B.

Re: How to calculate the CRC32 of 1 by hand?

Posted: 17 Mar 2019, 06:03
by afe
Where does the basis of your algorithm come from?

This is my hand calculation step according to the algorithm of CRC-8/CRC-16.

Input data: 0x1 = 0b00000001

polynomial: 100000100110000010001110110110111


append:

Code: Select all

0000000100000000000000000000000000000000
        --------------------------------
                                     32
XOR:

Code: Select all

0000000100000000000000000000000000000000
       100000100110000010001110110110111
---------------------------------------
       000000100110000010001110110110111  =  0x4C11DB7
The CRC value is 4C11DB7.

Re: How to calculate the CRC32 of 1 by hand?  Topic is solved

Posted: 17 Mar 2019, 06:28
by jeeswg
Here are some calculations:

Code: Select all

calculate the CRC-32 hash for hex '01':

inputs:
dividend: binary for hex '01': 0b00000001 = 0x01 = 1
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7

0b00000001 = 0x01
reverse bits in each byte:
0b10000000 = 0x80
append 32 0 bits:
0b1000000000000000000000000000000000000000 = 0x8000000000
XOR the first 4 bytes with 0xFFFFFFFF:
0b0111111111111111111111111111111100000000 = 0x7FFFFFFF00

'CRC division':
0111111111111111111111111111111100000000
 100000100110000010001110110110111 = poly (1)
 ---------------------------------
  111110110011111011100010010010110 = 'bits above poly (1)' ^ poly
  100000100110000010001110110110111 = poly (2)
  ---------------------------------
   111100101011110011011001001000010 = 'bits above poly (2)' ^ poly
   100000100110000010001110110110111 = poly (3)
   ---------------------------------
    111000011011100010101111111101010 = 'bits above poly (3)' ^ poly
    100000100110000010001110110110111 = poly (4)
    ---------------------------------
     110001111011000001000010010111010 = 'bits above poly (4)' ^ poly
     100000100110000010001110110110111 = poly (5)
     ---------------------------------
      100010111010000110011001000011010 = 'bits above poly (5)' ^ poly
      100000100110000010001110110110111 = poly (6)
      ---------------------------------
          100111000001000101111101011010 = 'bits above poly (6)' ^ poly = remainder

remainder: 0b00100111000001000101111101011010 = 0x27045F5A
XOR the remainder with 0xFFFFFFFF:
0b11011000111110111010000010100101 = 0xD8FBA0A5
reverse bits:
0b10100101000001011101111100011011 = 0xA505DF1B

thus the CRC-32 hash for hex '01' is 0xA505DF1B
I cite various sources in my tutorial, however, I did not come across any official sources.

Here is some code to do the calculations by hand: [EDIT: See improved code underneath.]

Code: Select all

q:: ;calculate CRC-32 hashes by hand
vBin := "0111111111111111111111111111111100000000"
vPoly := "100000100110000010001110110110111"
vLenPoly := StrLen(vPoly)
vOutput := ""
Loop
{
	vBin := LTrim(vBin, "0")
	if (StrLen(vBin) < vLenPoly)
		break
	vTemp1 := SubStr(vBin, 1, vLenPoly)
	vTemp2 := SubStr(vBin, vLenPoly+1)
	vTemp1X := JEE_BinXor(vTemp1, vPoly)
	vBin := vTemp1X vTemp2
	vOutput .= vTemp1X " " vTemp2 " " JEE_BinToHex(vTemp1X) "`r`n"
}
vBin := LTrim(vBin, "0")
vOutput .= "`r`n" vBin " " JEE_BinToHex(vBin)
vBin := JEE_BinXor(vBin, "11111111111111111111111111111111") ;0xFFFFFFFF
vOutput .= "`r`n" vBin " " JEE_BinToHex(vBin)
vBin := JEE_StrReverse(vBin)
vOutput .= "`r`n" vBin " " JEE_BinToHex(vBin)
Clipboard := vOutput "`r`n"
MsgBox, % "done"
return

JEE_BinXor(vBin1, vBin2)
{
	local
	vLen := Max(StrLen(vBin1), StrLen(vBin2))
	vBin1 := Format("{:0" vLen "}", vBin1)
	vBin2 := Format("{:0" vLen "}", vBin2)
	vOutput := ""
	Loop, % vLen
		vOutput .= !(SubStr(vBin1, A_Index, 1) = SubStr(vBin2, A_Index, 1))
	;MsgBox, % vBin1 "`r`n" vBin2 "`r`n" vOutput
	return vOutput
}

;JEE_Bin2Hex
JEE_BinToHex(vBin)
{
	local
	vIndex := StrLen(vBin)

	;bin2dec
	vOutput := 0
	Loop, Parse, vBin
	{
		vIndex--
		vOutput += A_LoopField * (2**vIndex)
	}

	;dec2hex
	return Format("{:X}", vOutput)
}

JEE_StrReverse(vText)
{
	local
	vLen := StrLen(vText)
	vOutput := ""
	VarSetCapacity(vOutput, vLen*2)

	Loop, % vLen
		vOutput .= SubStr(vText, vLen-A_Index+1, 1)
		;vOutput .= SubStr(vText, vLen--, 1) ;could use
	return vOutput
}
[EDIT:] Here is some improved code to do the calculations by hand:

Code: Select all

q:: ;calculate CRC-32 hashes by hand
vBin := "00000001"
vPoly := "100000100110000010001110110110111"

vOutput := vBin "`r`n"

vTemp := vBin, vBin := ""
Loop, % Ceil(StrLen(vTemp/8))
	vBin .= JEE_StrReverse(SubStr(vTemp, A_Index*8-7, 8))
vOutput .= vBin "`r`n"

vBin .= Format("{:032}", 0)
vOutput .= vBin "`r`n"

vTemp1 := SubStr(vBin, 1, 32)
vTemp2 := SubStr(vBin, 33)
vBin := JEE_BinXor(vTemp1, "11111111111111111111111111111111") vTemp2 ;0xFFFFFFFF
vOutput .= vBin "`r`n`r`n"

vOutput .= vBin "`r`n"
vLenPoly := StrLen(vPoly)
vBarrier := ""
Loop, % vLenPoly
	vBarrier .= "-"
vIndent := ""
Loop, % InStr(vBin, "1") - 1
	vIndent .= " "
vBin := LTrim(vBin, "0")
vOutput .= vIndent vPoly "`r`n" vIndent vBarrier "`r`n"
Loop
{
	vTemp1 := SubStr(vBin, 1, vLenPoly)
	vTemp2 := SubStr(vBin, vLenPoly+1)
	vTemp1X := JEE_BinXor(vTemp1, vPoly)
	vBin := vTemp1X vTemp2
	Loop, % InStr(vBin, "1") - 1
		vIndent .= " "
	vBin := LTrim(vBin, "0")
	if (StrLen(vBin) < vLenPoly)
		break
	vOutput .= vIndent SubStr(vBin, 1, vLenPoly) "`r`n" vIndent vPoly "`r`n" vIndent vBarrier "`r`n"
}
vOutput .= vIndent SubStr(vBin, 1, vLenPoly) "`r`n"

vBin := LTrim(vBin, "0")
vBin := Format("{:032}", vBin)
vOutput .= "`r`n" vBin " " JEE_BinToHex(vBin)
vBin := JEE_BinXor(vBin, "11111111111111111111111111111111") ;0xFFFFFFFF
vOutput .= "`r`n" vBin " " JEE_BinToHex(vBin)
vBin := JEE_StrReverse(vBin)
vOutput .= "`r`n" vBin " " JEE_BinToHex(vBin)
Clipboard := vOutput "`r`n"
MsgBox, % "done"
return

JEE_BinXor(vBin1, vBin2)
{
	local
	vLen := Max(StrLen(vBin1), StrLen(vBin2))
	vBin1 := Format("{:0" vLen "}", vBin1)
	vBin2 := Format("{:0" vLen "}", vBin2)
	vOutput := ""
	Loop, % vLen
		vOutput .= !(SubStr(vBin1, A_Index, 1) = SubStr(vBin2, A_Index, 1))
	;MsgBox, % vBin1 "`r`n" vBin2 "`r`n" vOutput
	return vOutput
}

;JEE_Bin2Hex
JEE_BinToHex(vBin)
{
	local
	vIndex := StrLen(vBin)

	;bin2dec
	vOutput := 0
	Loop, Parse, vBin
	{
		vIndex--
		vOutput += A_LoopField * (2**vIndex)
	}

	;dec2hex
	return Format("{:X}", vOutput)
}

JEE_StrReverse(vText)
{
	local
	vLen := StrLen(vText)
	vOutput := ""
	VarSetCapacity(vOutput, vLen*2)

	Loop, % vLen
		vOutput .= SubStr(vText, vLen-A_Index+1, 1)
		;vOutput .= SubStr(vText, vLen--, 1) ;could use
	return vOutput
}

Re: How to calculate the CRC32 of 1 by hand?

Posted: 17 Mar 2019, 06:41
by afe
XOR the first 4 bytes with 0xFFFFFFFF:
Where does this basis come from?

I have read this paper
http://www.ross.net/crc/crcpaper.html
, but until now I can't find the official documentation for CRC-32.

Re: How to calculate the CRC32 of 1 by hand?

Posted: 17 Mar 2019, 07:57
by jeeswg
These are the best 3 sources I found:

[explains 'CRC division']
crc_v3.txt
http://www.ross.net/crc/download/crc_v3.txt

[calculates the CRC-32 hash for ASCII 'a', i.e. hex '97']
How to calculate CRC32 by hand? – An Integrated World
https://www.anintegratedworld.com/how-to-calculate-crc32-by-hand/

[the procedure neatly summarised]
c - How is a CRC32 checksum calculated? - Stack Overflow
https://stackoverflow.com/a/44805358

Re: How to calculate the CRC32 of 1 by hand?

Posted: 17 Mar 2019, 13:46
by afe
Thank you very much!

Re: How to calculate the CRC32 of 1 by hand?

Posted: 23 Mar 2019, 09:28
by afe
jeeswg wrote:
17 Mar 2019, 07:57
These are the best 3 sources I found:
I am having trouble calculating a two-byte crc-32, I don't know where the problem is. Please advise.

Code: Select all

00000001 00000010      ; Input binary bytes
01000000 10000000      ; Input reflected
01000000 10000000 00000000 00000000 00000000 00000000      ; Fill 32 zeros

; xor
11111111 11111111 11111111 11111111                                    ; Initial Value: 0xFFFFFFFF
01000000 10000000 00000000 00000000 00000000 00000000
-------------------------------------------------------------------------
10111111 01111111 11111111 11111111 00000000 00000000
10000010 01100000 10001110 11011011 1                                  ; Polynomial: 0x104C11DB7
-------------------------------------------------------------------------
   111101000111110111000100100100100
   100000100110000010001110110110111
---------------------------------------------------
     111011000011101010010100100100110
     100000100110000010001110110110111
---------------------------------------------------
      110111001011010000110100100100010
      100000100110000010001110110110111
      -----------------------------------------------
       101111011010100101110100100101010
       100000100110000010001110110110111
-----------------------------------------------------
        111111110010011111101001001110100
        100000100110000010001110110110111
-----------------------------------------------------
         111110101000111011001111110000110
         100000100110000010001110110110111
-------------------------------------------------------
          111100011101110010000010001100010
          100000100110000010001110110110111
-------------------------------------------------------
           111001110111100000011001110101010
           100000100110000010001110110110111
--------------------------------------------------------
            110010100011000100101110000111010
            100000100110000010001110110110111
--------------------------------------------------------
             100100001010001101000001100011010
             100000100110000010001110110110111
----------------------------------------------------------
              100101100001111001111010101101000
              100000100110000010001110110110111
----------------------------------------------------------
                 101000111111011110100011011111                   ; Remainder
               11111111111111111111111111111111                   ; Final Xor Value: 0xFFFFFFFF
-----------------------------------------------------------
               11010111000000100001011100100000
               00000100111010000100000011101011 = 0x4E840EB    ; Result reflected
But the actual value should be 0xB6CC4292.

Re: How to calculate the CRC32 of 1 by hand?

Posted: 23 Mar 2019, 09:44
by jeeswg
- So your input is: 0b0000000100000010 = 0x0102, which according to: https://crccalc.com/ has CRC-32 hash 0xB6CC4292.
- I have an example that does 2 bytes in my tutorial, it does the 2-byte ASCII string 'ab' in one go. You should be able to pretty much verbatim use that as a template. There's also the code I wrote above that might be helpful.
- Your example is a bit confusing to read because you haven't stripped any internal spaces, this could easily lead to an error somewhere down the line.

Re: How to calculate the CRC32 of 1 by hand?

Posted: 23 Mar 2019, 14:14
by afe
I am dealing with the input message as a whole and the xor calculation is no problem. It seems that there is a problem with the algorithm itself.

How to process two bytes 00000001 00000010 together instead of calculating one byte at a time?
The algorithm below does not seem right.

Code: Select all

00000001 00000010     ; input
01000000 10000000     ; reflected

01000000 10000000 00000000 00000000 00000000 00000000      ; padded
11111111 11111111 11111111 11111111                                    ; 0xFFFFFFFF
-------------------------------------------------------------------------
10111111 01111111 11111111 11111111 00000000 00000000

Re: How to calculate the CRC32 of 1 by hand?

Posted: 23 Mar 2019, 17:23
by jeeswg
I think your problem is that at the beginning you must reverse the bits in each byte (8-bit chunks), whereas at the end you must reverse the bits in a 4-byte chunk as a whole (a 32-bit chunk).

Here are some calculations:

Code: Select all

calculate the CRC-32 hash for hex '0102':

inputs:
dividend: binary for hex '0102': 0b0000000100000010 = 0x0102
polynomial: 0b100000100110000010001110110110111 = 0x104C11DB7

0000000100000010
reverse bits in each byte:
1000000001000000
append 32 0 bits:
100000000100000000000000000000000000000000000000
XOR the first 4 bytes with 0xFFFFFFFF:
011111111011111111111111111111110000000000000000

'CRC division':
011111111011111111111111111111110000000000000000
 100000100110000010001110110110111
 ---------------------------------
  111110100011111011100010010010110
  100000100110000010001110110110111
  ---------------------------------
   111100001011110011011001001000010
   100000100110000010001110110110111
   ---------------------------------
    111001011011100010101111111101010
    100000100110000010001110110110111
    ---------------------------------
     110011111011000001000010010111010
     100000100110000010001110110110111
     ---------------------------------
      100110111010000110011001000011010
      100000100110000010001110110110111
      ---------------------------------
         110011100000100010111110101101000
         100000100110000010001110110110111
         ---------------------------------
          100110001101000001100000110111110
          100000100110000010001110110110111
          ---------------------------------
             110101011000011101110000001001000
             100000100110000010001110110110111
             ---------------------------------
              101011111100111111111101111111110
              100000100110000010001110110110111
              ---------------------------------
                10110110101111011100110010010010

remainder: 0b10110110101111011100110010010010 = 0xB6BDCC92
XOR the remainder with 0xFFFFFFFF:
0b01001001010000100011001101101101 = 0x4942336D
reverse bits:
0b10110110110011000100001010010010 = 0xB6CC4292

thus the CRC-32 hash for hex '0102' is 0xB6CC4292
I've updated the code above, it now generates the 'CRC division' calculation, complete with indentation. It does all the gruesome work for you. A good use of automation. Cheers.

Re: How to calculate the CRC32 of 1 by hand?

Posted: 24 Mar 2019, 03:30
by afe
Thank you very much.
I misunderstood "Reverse". It should reverse each byte instead of inverting this message.
Thanks again.

Code: Select all

00000001 00000010     ; input
10000000 01000000     ; reflected

10000000 01000000 00000000 00000000 00000000 00000000      ; padded
11111111 11111111 11111111 11111111                                    ; 0xFFFFFFFF
-------------------------------------------------------------------------
01111111 10111111 11111111 11111111 00000000 00000000