Can the propeller be used as a CAN sniffer? (bit collection project idea)
turbosupra
Posts: 1,088
I'd like to build a Prop Sniffer. Toyota has a CAN like network called Bo dy Electronic Area Net work and it is not encrypted. It uses 2 multiplex lines, MPX1 and MPX2. For those of you that have done something like this, or are more experienced than I, is this feasible?
The specification for the network is
1 SOF (1 bit) (start of frame)
2-5 PRI (4 bits) (priority of bits)
6-9 ML (4 bits) (message length, length of message and number of bytes, [ID + DATA] (3-13)
10-17 DST-ID (8 bits) (the id showing the communication destination)
18-25 MES-ID (8 bits) (is an area showing message contents)
26-113 DATA (8 to 88 bits) (1 to 11 bytes of data, variable length, could be as small as bits 26-33, reskewing the bit number slots for the remaining bit groups)
114-121 CRC (8 bits) (error check code remainder from polynomial)
122-129 EOM (8 bits) (end of message and controls time to prepare response for sending)
130-132 RSP (2 bits) (represents the response area)
133-138 EOF (6 bits) (shows the end of the frame)
More specs
CSMA/CD
Bit encoding: NRZ
Media Access: Contention
Error Detection: 8-bit CRC
Header Length: 25bits
Data length: 1-11bytes
Overhead: 28%
In-message response: NO
Bit rate: 10Kb/s
Maximum Bus Length: Not Specified
Maximum Nodes: 20
u Needed?: YES
Sleep / Wakeup: NO
H/W Avail?: YES (?)
Cost: Low
Communication speed: Max 10kbps
Communication wire: av single wire
Drive type: single wire voltage drive
Data length: 1-11 byte (variable)
It also employs bit stuffing where an inverted bit is inserted when 5 consecutive bits have the same value from the SOF to CRC bit groups
With that being said, could the prop monitor the lines for binary and convert it to hex? I'd like to reverse engineer the CRC poly as well once I get this information so that I could send my own messages. On the net I found partial examples of data captured by them, that data is in quotes below.
The specification for the network is
1 SOF (1 bit) (start of frame)
2-5 PRI (4 bits) (priority of bits)
6-9 ML (4 bits) (message length, length of message and number of bytes, [ID + DATA] (3-13)
10-17 DST-ID (8 bits) (the id showing the communication destination)
18-25 MES-ID (8 bits) (is an area showing message contents)
26-113 DATA (8 to 88 bits) (1 to 11 bytes of data, variable length, could be as small as bits 26-33, reskewing the bit number slots for the remaining bit groups)
114-121 CRC (8 bits) (error check code remainder from polynomial)
122-129 EOM (8 bits) (end of message and controls time to prepare response for sending)
130-132 RSP (2 bits) (represents the response area)
133-138 EOF (6 bits) (shows the end of the frame)
More specs
CSMA/CD
Bit encoding: NRZ
Media Access: Contention
Error Detection: 8-bit CRC
Header Length: 25bits
Data length: 1-11bytes
Overhead: 28%
In-message response: NO
Bit rate: 10Kb/s
Maximum Bus Length: Not Specified
Maximum Nodes: 20
u Needed?: YES
Sleep / Wakeup: NO
H/W Avail?: YES (?)
Cost: Low
Communication speed: Max 10kbps
Communication wire: av single wire
Drive type: single wire voltage drive
Data length: 1-11 byte (variable)
It also employs bit stuffing where an inverted bit is inserted when 5 consecutive bits have the same value from the SOF to CRC bit groups
With that being said, could the prop monitor the lines for binary and convert it to hex? I'd like to reverse engineer the CRC poly as well once I get this information so that I could send my own messages. On the net I found partial examples of data captured by them, that data is in quotes below.
DID 62
MID BF
DATA1 00
CRC 78
EOM 7E
DID 62
MID D2
DATA1 00
DATA2 A0
DATA3 08
CRC 0A
EOM 7E
DID 98
MID CC
DATA1 02
DATA2 A8
CRC 35
EOM 7E
DID EF
MID 6A
DATA1 04
CRC 44
EOM 3F
Comments
so how much time is there to process the bits - and then the message ...
I tested everything with a USB-CAN interface called PCAN (provided by client). In the end, the object I wrote was used for node-to-node comms in an HVAC system.
There is a software CAN object somewhere, that only requires the interface chip (MCP2551, 8-pin DIP in photo). I've not used it, but it might be worth looking at. I went the full hardware route because I had been asked to code a client project with that circuit and it worked very well.
Standard frame: CRC delimiter RTR │ ACK SOF │ IDE Data length (0 - 8 bytes) │ │ ACK delimiter │ Ident A │ │ R0 │ Byte 0 Byte 1 Byte 2 Byte 3 Byte 4 Byte 5 Byte 6 Byte 7 CRC │ │ │ EOF │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ 0_xxxxxxxxxxx_0_0_0_xxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxxxxxxxxx_1_i_1_1111111So while the signalling might be similar, the protocol appears completely different.I've written a few Prop-based objects that should work with some modifications to the parse_bit routine in the reader section.
What are the signal levels?
Does it idle high or low?
Are the bits inverted?
You may not even need the 2551 line driver. I'm currently working on a modification to the above CANbus routines that'll work with a GMLAN class-2 databus, which uses the same CAN protocol, but the messages are inverted, uses 5V for dominant '0' bits and gnd for recessive '1' bits, so all I need for that is a transistor driver for tx, and a current limiter for rx.
I was able to ask for more complete data sets that the person used matlab to get.
Did you use a scope to gather your information, or can I use a scope to answer the questions you've asked me?
Using the first code set
PRI | DATA (variable RSP SOF| ML DID MID | length) CRC EOM | EOF | | | | | | | | | | x_xxxx_xxxx_xxxxxxxx_xxxxxxxx_[8 to 88 bits]_xxxxxxxx_xxxxxxxx_xx_xxxxxxYou show a Standard Frame and say it's the only frame kind that the MCP2515 decodes. Did you omit the Extended Frame kind or have you encountered problems with the MCP2515 and Extended Frames?
Thanks
Do you know if it is CAN?
If yes, then the MCP2551 or similar would do for the interface chip.
But your mention here seems to not be CAN COuld it be LIN?
At 10kbs the prop should handle it fine.
Initially it might be better to snoop the bus/line(s) using an optoisolator - a 6N137 or similar should do the job.
For the CRC, often the address/header is not included in the CRC. Check the CAN bus spec as this might be the CRC used.
There are online calculators that include setting the CRC algorithm and using that, hopefully you can determine which CRC is used. There are only a few common ones.
Since it is only a single byte CRC it may just be a simple XOR function.
I managed to find a CRC that works with two of your messages, but fails all of the others, not sure what to make of that. Every search for more info about this BEAN protocol sends me to the SAE paywalled paper.
CON _clkmode = xtal1 + pll16x _xinfreq = 5_000_000 CRC8 = %100010011 OBJ fds : "FullDuplexSerial" DAT message1 byte "10101001111010010110010000000000011101001",00 message1d byte "0101001111010010110010000000000011101001",00 ' 100010011 ignore the start bit message2 byte "1011000111101001000101100000000001011010110110101",00 message2d byte "011000111101001000101100000000001011010110110101",00 ' none found message3 byte "1011001001001100011001100000000101010011111010100",00 message3d byte "011001001001100011001100000000101010011111010100",00 ' 100010011 message4 byte "01100010110111110000000001111000",00 message5 byte "011000101101001000000000101000000000100000001010",00 ' none found message6 byte "1001100011001100000000101010100000110101",00 ' none found message7 byte "1110111101101010000001000100010000111111",00 ' none found PUB main | i, temp, crc_result, length, crc fds.start(31,30,0,115200) waitcnt(cnt + clkfreq) fds.tx($00) temp := 0 length := strsize(@message1d) crc := 0 repeat crc++ crc_result := 0 temp := 0 repeat i from 0 to length - 1 temp := message1d[i] - "0" crc_result := crc_result << 1 | temp if crc_result => %100000000 crc_result := crc_result ^ CRC if crc_result == 0 fds.str(string("Valid CRC = ")) fds.bin(crc,9) repeat if crc > %111111111 fds.str(string("None found")) repeat PUB check | i, temp, crc_result, length, crc crc_result := 0 temp := 0 length := strsize(@message3d) fds.tx($0D) repeat i from 0 to length - 1 temp := message3d[i] - "0" crc_result := crc_result << 1 | temp if crc_result => %100000000 crc_result := crc_result ^ CRC8 fds.bin(crc_result,17) fds.tx($0D) repeatThe above code stops searching once the CRC reaches 10 bits. I'm currently (for the past half-hour) letting it run up to the full 32 bits just to see.@ksltd
Extended and remote frames work fine; I didn't see a reason to show them as they closely resemble the standard frame, and are nothing like what turbosupra is describing:
Standard frame: CRC delimiter RTR | ACK SOF | IDE Data length (0 - 8 bytes) | | ACK delimiter | Ident A | | R0 | Byte 0 Byte 1 Byte 2 Byte 3 Byte 4 Byte 5 Byte 6 Byte 7 CRC | | | EOF | | | | | | | | | | | | | | | | | | | 0_xxxxxxxxxxx_0_0_0_xxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxxxxxxxxx_1_i_1_1111111 Extended frame: CRC delimiter SRR RTR | ACK SOF | IDE | R1 Data length | | ACK delimiter | Ident A | | Ident B | | R0 | Byte 0 Byte 1 Byte 2 Byte 3 Byte 4 Byte 5 Byte 6 Byte 7 CRC | | | EOF | | | | | | | | | | | | | | | | | | | | | | 0_xxxxxxxxxxx_1_1_xxxxxxxxxxxxxxxxxx_0_0_0_xxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxx_xxxxxxxxxxxxxxx_1_i_1_1111111 Standard remote frame: CRC delimiter RTR | ACK SOF | IDE Data length | | ACK delimiter | Ident A | | R0 | CRC | | | EOF | | | | | | | | | | | 0_xxxxxxxxxxx_1_0_0_0000_xxxxxxxxxxxxxxx_1_i_1_1111111 Extended remote frame: CRC delimiter SRR RTR | ACK SOF | IDE | R1 Data length | | ACK delimiter | Ident A | | Ident B | | R0 | CRC | | | EOF | | | | | | | | | | | | | | 0_xxxxxxxxxxx_1_1_xxxxxxxxxxxxxxxxxx_1_0_0_0000_xxxxxxxxxxxxxxx_1_i_1_1111111Chris
That does not sound like CAN, looks like a Custom Automotive Network, using LIN bus hardware drivers
(which are 10KHz region, single pin, 12V signaling)
You might like to change the heading from CAN
I'd also suggest you look into LIN bus a little, even if this is not a LIN clone, LIN has things like an Autobaud preamble this might use.
10KHz is quite low speed, so I'd suggest doing a Bridge device in a Prop - that can Read/Write on this bus, and converts to a Generic UART PC serial stream.
eg One simple way is to nibble encode, where lower 4 bits are a half byte payload, and the upper 4 bits give 16 choices of what to do with it. 2 of those can tag DataH,DataL, which leaves 14 spare for control and commands
That allows the complex reverse engineering stuff to be managed on a PC, which is MUCH easier than a microcontroller.
You need to run the PC link at > 2x the Toyota bus, with some buffering, but 10KHz is very slow.
I'm struggling trying to understand the code and decode process from start to finish, which bits are computed for message length, which are computed for the CRC, why you need the RSP field, how you know what the SOF bit is and similar questions. I'm going to try and read your code and see what you've done, why do you have ,00 at the end of the string in SPIN, is that to terminate the byte? How does bit stuffing work? How would the receiver know if you had 1111111 but bit stuffing translated it to 1111011 or 11111011 (depending if it inserts or replaces)? And that it wasn't originally 1111011 or 11111011 (depending on if it inserts or replaces) in the first place?
About the B.E.A.N protocol, it was said to
Here are the SAE papers for you
https://drive.google.com/folderview?id=0B7FYCjMZX9RtejhDbGRvRGo5RVE&usp=sharing
For the 00 at the end of the strings, I've written all of the messages as text strings to allow me to parse one bit at a time, and the 00 is a null-terminator so Spin knows where the end of the string is.
For bit stuffing, the bus is non-return-to-zero, and there is no clock line, so it relies on transitions in order to maintain synchronization. If there are no transitions for five bits, a stuffed, opposite, bit is inserted in order to force a transition. A sequence of 1111100000 will be stuffed as 111110000010, where the underlined bits are stuffed. To unstuff, if you count five similar bits in a row, discard the bit that follows. 111110111110000 unstuffs to 1111111111000. The exception to that where you might see six or more identical bits in a row is in error-frames (at least with CAN) and also for end-of-frame.
I'll hopefully know more after I get a chance to study the papers.
Chris
I'm going to wrap my head around the bit stuffing a little more, thank you for the explanation though. I need to see it in practice and working to really feel confident in how it works. I'll keep studying, thank you.
-------- PRI|ML 53 [b]0101[/b] for the first nibble, [b]0011[/b] for the second nibble - 5 and 3 DID D2 11010010 (field 1) MID C8 11001000 (field 2) = 00011010 DATA1 00 00000000 (field 3) CRC E9 check crc: E9 11101001 CRC OK EOM 7E -------- PRI|ML 63 [b]0110[/b] for the first nibble, [b]0011[/b] for the second nibble - 6 and 3 DID D2 11010010 (field 1) MID 2C 00101100 (field 2) = 11111110 DATA1 00 00000000 (field 3) CRC B5 check crc: B5 CRC OK EOM 7E -------- PRI|ML 64 [b]0110[/b] for the first nibble, [b]0100[/b] for the second nibble - 6 and 4 DID 98 (field 1) MID CC (field 2) DATA1 02 (field 3) DATA2 A7 (field 4) CRC D4 check crc: D4 CRC OK EOM 7E --------*In the set below, italicized means I'm guessing at this field
Maybe bit stuffing plays into it?
How could the DID + MID be an initialization pattern for the CRC polynomial? Below are the combos I have tried, I cannot find a pattern.
-------- PRI|ML 53 0101 0011 5 and 3 DID D2 11010010 (field 1) MID C8 11001000 (field 2) = 00011010 DATA1 00 00000000 (field 3) CRC E9 check crc: E9 OR 11101001 CRC OK EOM 7E DID + MID + DATA = D2C800 OR 110100101100100000000000 ' Valid CRC = 101011100 PRI + ML + DID + MID + DATA = 53D2C800 OR 01010011110100101100100000000000 ' Valid CRC = 100000000 PRI + ML + DID + MID + DATA + CRC = 53D2C800E9 OR 0101001111010010110010000000000011101001 ' Valid CRC = 100010011 (PRI/ML XOR) + DID + MID + DATA = 110110100101100100000000000 ' Valid CRC = 100000000 (PRI/ML XOR) + DID + MID + DATA + CRC = 11011010010110010000000000011101001 ' None found PRI + ML + (DID/MID XOR) + DATA = 010100110001101000000000 ' Valid CRC = 10101110 PRI + ML + (DID/MID XOR) + DATA + CRC = 01010011000110100000000011101001 ' Valid CRC = 100000000 ML + DID + MID + DATA = 0011110100101100100000000000 ' Valid CRC = 101010000 ML + DID + MID + DATA + CRC = 001111010010110010000000000011101001 ' Valid CRC = 100010110 -------- PRI|ML 63 0110 0011 6 and 3 DID D2 11010010 (field 1) MID 2C 00101100 (field 2) = 11111110 DATA1 00 00000000 (field 3) CRC B5 check crc: B5 OR 10110101 CRC OK EOM 7E DID + MID + DATA = D22C00 OR 110100100010110000000000 ' Valid CRC = 10101110 PRI + ML + DID + MID + DATA = 63D22C00 OR 01100011110100100010110000000000 ' Valid CRC = 100010011 PRI + ML + DID + MID + DATA + CRC = 63D22C00B5 OR 0110001111010010001011000000000010110101 ' None found (PRI/ML XOR) + DID + MID + DATA = 00000101110100100010110000000000 ' Valid CRC = 101011100 (PRI/ML XOR) + DID + MID + DATA + CRC = 0000010111010010001011000000000010110101 ' Valid CRC = 101011100 PRI + ML + (DID/MID XOR) + DATA = 011000111111111000000000 ' Valid CRC = 10101110 PRI + ML + (DID/MID XOR) + DATA + CRC = 01100011111111100000000010110101 ' Valid CRC = 100000000 ML + DID + MID + DATA = 0011110100100010110000000000 ' Valid CRC = 100010110 ML + DID + MID + DATA + CRC = 001111010010001011000000000010110101 ' Valid CRC = 100010110 -------- PRI|ML 64 0110 0100 6 and 4 DID 98 10011000 (field 1) MID CC 11001100 (field 2) = 1010100 DATA1 02 00000010 (field 3) DATA2 A7 10100111 (field 4) CRC D4 check crc: D4 OR 11010100 CRC OK EOM 7E DID + MID + DATA = 98CC02A7 OR 10011000110011000000001010100111 ' Valid CRC = 100000000 PRI + ML + DID + MID + DATA = 6498CC02A7 OR 0110010010011000110011000000001010100111 ' Valid CRC = 10001001 PRI + ML + DID + MID + DATA + CRC = 6498CC02A7D4 OR 011001001001100011001100000000101010011111010100 ' None found (PRI/ML XOR) + DID + MID + DATA = 000000101001100011001100000000101010011111010100 ' None found (PRI/ML XOR) + DID + MID + DATA + CRC = 00000010100110001100110000000010101001111101010011010100 ' None found PRI + ML + (DID/MID XOR) + DATA = 0110010010101000000001010100111 ' Valid CRC = 1000000 PRI + ML + (DID/MID XOR) + DATA + CRC = 011001001010100000000101010011111010100 ' Valid CRC = 100110110 ML + DID + MID + DATA = 010010011000110011000000001010100111 ' Valid CRC = 100010110 ML + DID + MID + DATA + CRC = 01001001100011001100000000101010011111010100 ' None found --------I also didn't realize that messages 4 through 7 were posted without a priority and message length, and I mis-copied some of those as well. Message 6 matches when prefaced with a priority 6 and message length 4 %01100100.
Frustratingly, I still can't get matches to messages 4, 5, or 7 even trying every priority from $0 to $F. A couple messages matching to the same polynomial might be a coincidence, but 4 out of 7?
I've tried inverting, I've tried without headers, I've tried subtractions instead of xor's, I've tried comparing to => crc instead of => $100; nothing gives as consistent a result as with header, non-inverted, xor'ing when => $100.
Stuffed bits cannot be part of the CRC, as the CRC field may also be stuffed. I dunno why priority and message-length wouldn't be part of the calculation, but omitting them doesn't seem to help.
I had guessed at the message length and verified it in the paper you posted. The paper also shows a typical bitstream with levels for SOF, EOM, and EOF, so I should be able to get a reader coded from that.
My CRC calculator wasn't very well thought out, stopping at the first positive match. This should be easier to use.
DAT message1 byte "0101001111010010110010000000000011101001",00 ' 53, D2, C8, 00, E9 message2 byte "0110001111010010001011000000000010110101",00 ' 63, D2, 2C, 00, B5 message3 byte "011001001001100011001100000000101010011111010100",00 ' 64, 98, CC, 02, A7, D4 message4 byte "____001101100010101111110000000001111000",00 ' _3, 62, BF, 00, 78 message5 byte "____0101011000101101001000000000101000000000100000001010",00 ' _5, 62, D2, 00, A0, 08, 0A message6 byte "011001001001100011001100000000101010100000110101",00 ' 64, 98, CC, 02, A8, 35 message7 byte "____001111101111011010100000010001000100",00 ' _3, EF, 6A, 04, 44 PUB main | i, temp, crc_result, length, crc, message fds.start(31,30,0,115_200) waitcnt(cnt + clkfreq) fds.tx($00) message := @message1 temp := 0 length := strsize(message) crc := 0 repeat until crc == %1_1111_1111 crc++ crc_result := 0 temp := 0 repeat i from 0 to length - 1 temp := byte[message][i] - "0" crc_result := crc_result << 1 | temp if crc_result => %1_0000_0000 crc_result := crc_result ^ crc if crc_result == 0 fds.str(string("Valid CRC = ")) fds.bin(crc,9) fds.tx($09) fds.hex(crc,3) fds.tx($0D) fds.str(string("Finished"))ChrisThe other hint I was given (and didn't realize until today) was that it had something to do with encryption. The person that said they've cracked it said to check out this site
http://cryptopals.com/
Have you ever seen a CRC that could been encrypted by the MID and DID? Could that be what this means? Maybe repeating key XOR? Or an XOR of the MID and DID used in the repeating key, or a single byte XOR cipher? The single byte xor cipher makes the most sense based on what was written below I think?
I'm modifying my GMLAN reader to work with BEAN, but I really need to see an actual signal from an o'scope as the tech paper doesn't really say much about it.
The papers show the frame format in figure 9 with high and low levels for each bit field. According to that figure, the bus idles low.
However figure 3 shows a bus interface circuit with what looks like a pull-up resistor and a transistor driver to assert a low. It also labels the connections to the microcontroller as Rx-not and Tx-not.
Kinda hard to tell what's going on in the interface circuit in figure 7 but that one appears to be biased low, with Tx asserting a high.
Then I can try and insert the poly and see what happens?
I have an ECU that uses bean, I'll have to fabricate something up for it and try and get you an Oscope, the only problem is that I have a propscope and I don't think it will record/archive data, it just displays it onscreen.
Shift the bitstream left into a working register
If bit 8 of the working register is set, then xor it with the polynomial
Repeat until all bits are shifted
That's for decoding. To encode it, repeat the loop until the entire bitstream has been shifted plus eight "0" bits for the crc field. I've included an example in the latest code, which I've yet again modified to deal with strings of hexadecimal characters rather than binary.
A screen capture of the propscope should be fine. Just hit 'printscreen', create a new bitmap image, edit in ms-paint, paste the captured image, save as jpg. Simple.
CRC calculator 2.spin
I usually do screen caps with my prop scope, so if that is sufficient, I will do that in this case as well.
fds.bin(nib, 32) fds.str(string(" - nib")) fds.tx(13) fds.bin(crc_result, 32) fds.str(string(" - crc_result before")) fds.tx(13) crc_result := crc_result << 1 | (nib <-= 1) & 1 ' Shift crc_result left one bit and append the most-significant bit of nib, rotate nib to get the next msb fds.bin(nib, 32) fds.tx(13)} fds.bin(crc_result, 32) fds.str(string(" - crc_result after")) fds.tx(13) fds.tx(13)So is the basic premise to
1.) count the number of hex digits
2.) go into a loop based on that count
3.) get first hex digit, get first character, get 4 digit binary value of that character
4.) bit shift the nibble lsb to the nibble msb 4 times in a loop
5.) bit shift the crc_result bits 4 to 0 shifted to 8-4
6.) append the bits from the nibble to the crc_result bits 3-0
7.) Xor them with the crc you are testing
8.) If the Xor value is 0, the crc is valid
What is the crc_result value before it is appended and where does it come from?
Why does the CRC8 have 9 values?
Why does it need that leading 1?
Is that to give it significant digits in case the value behind it is a 0?
Is the CRC field in the stream of bits a value that is calculated and inserted to allow the poly to work?
What is the crc_result value before it is appended and where does it come from?
The crc_result is initially zero, it's a working register that the bitstream is shifted into and xor'd with the polynomial.
Why does the CRC8 have 9 values?
Wikipedia has some good info on the Cyclic redundancy check. Regarding the naming convention for why CRC8 has nine bits: I suppose I should've been saying the polynomial is $13 rather than $113, but that's just an extra layer of confusion I didn't wanna deal with.
Is the CRC field in the stream of bits a value that is calculated and inserted to allow the poly to work?
The CRC field is calculated in the exact same manner as verifying the message. Suppose the bitstream from priority/message-length through the final data byte is $64, $98, $CC, $02, $A7. In order to get the crc field, append an empty byte to the end of the string to hold the crc, run it through the same process in the flowchart, and value remaining in the crc_result register will be $D4.
In other words:
Running the string $64, $98, $CC, $02, $A7, $00 through the flowchart process leaves $D4 in the crc_result register.
Running the string $64, $98, $CC, $02, $A7, $D4 through the flowchart process leaves $00 in the crc_result register.
Clear as mud?
using 113 or 100010011
5 = 01011111
3 = 00110101
D = 11000111
2 = 00100110
C = 11010100
8 = 10011000
0 = 00000000
0 = 00000000
E = 11110010
9 = 10001011
53 = 10011010
D2 = 10000010
C8 = 00011111
00 = 00000000
E9 = 01001010
53D2 = 00010100
C800E9 = 11101011
but
53D2C800E9 = 00000000
I'm going to keep reading and hope it clicks.
In order to find the crc field, every bit must be shifted, plus eight bits to hold the crc result. Simplest way to do that is to append an empty byte $00 to the end of the bitstream. |--05--||--00--| 000000000_0000010100000000 start 10100000000 shift left until bit 8 of working register is set 10100000000 shift 10100000000 shift 10100000000 shift 10100000000 shift 1_0100000000 shift 10_100000000 shift 101_00000000 shift 1010_0000000 shift 10100_000000 shift 101000_00000 shift 1010000_0000 shift 10100000_000 shift 101000000_00 shift - bit 8 set 100010011 xor 001010011_00 result 10100110_0 shift 101001100 shift - bit 8 set 100010011 xor 001011111 result, finished, all bits shifted, result = $5F Going the other way: |--05--||--5F--| %0000010101011111 000000000_0000010101011111 start 0_000010101011111 shift left until bit 8 of working register is set 00_00010101011111 shift 000_0010101011111 shift 0000_010101011111 shift 00000_10101011111 shift 000001_0101011111 shift 0000010_101011111 shift 00000101_01011111 shift 000001010_1011111 shift 000010101_011111 shift 000101010_11111 shift 001010101_1111 shift 010101011_111 shift 101010111_11 shift - bit 8 set 100010011 xor 001000100_11 result 10001001_1 shift 100010011 shift - bit 8 set 100010011 xor 000000000 result - finished, all bits shifted, result = $00After I read this, I was able to read through and understand the code block you put in your object as well. I'm going to start fresh and write code tomorrow and try to implement what you've taught me.
In the second code block, why do you take the extra step to xor the poly with the resulting xored value at the bottom? Is this to check your answer?
{{┌────────────────────────────────────┐ │ CRC calculator │ │ Author: Chris Gadd │ │ Copyright (c) 2014 Chris Gadd │ │ See end of file for terms of use. │ └────────────────────────────────────┘ 11101001 Using the message $53,$D2,$C8,$00,$E9 |--53--||--D2--||--C8--||--00--||--E9--| Rewritten in binary: 0101001111010010110010000000000011101001 Shift the bitstream 40 0 left into a new register | | until the bit 8 is set 000000000_0101001111010010110010000000000011101001 000000000_101001111010010110010000000000011101001 000000001_01001111010010110010000000000011101001 000000010_1001111010010110010000000000011101001 000000101_001111010010110010000000000011101001 000001010_01111010010110010000000000011101001 000010100_1111010010110010000000000011101001 000101001_111010010110010000000000011101001 001010011_11010010110010000000000011101001 010100111_1010010110010000000000011101001 Bit 8 is now set 101001111_010010110010000000000011101001 Xor with the polynomial 100010011 Result 001011100_010010110010000000000011101001 Shift left until bit 8 is set 010111000_10010110010000000000011101001 Bit 8 is set 101110001_0010110010000000000011101001 Xor with the polynomial 100010011 Result 001100010_0010110010000000000011101001 Shift 011000100_010110010000000000011101001 Bit 8 set 110001000_10110010000000000011101001 Xor 100010011 Result 010011011_10110010000000000011101001 Shift, bit 8 set 100110111_0110010000000000011101001 Xor 100010011 Result 000100100_0110010000000000011101001 Shift 001001000_110010000000000011101001 010010001_10010000000000011101001 Bit 8 set 100100011_0010000000000011101001 Xor 100010011 Result 000110000_0010000000000011101001 Shift 001100000_010000000000011101001 011000000_10000000000011101001 Bit 8 set 110000001_0000000000011101001 Xor 100010011 Result 010010010_0000000000011101001 Shift, bit 8 set 100100100_000000000011101001 Xor 100010011 Result 000110111_000000000011101001 Shift 001101110_00000000011101001 011011100_0000000011101001 Bit 8 set 110111000_000000011101001 Xor 100010011 Result 010101011_000000011101001 Shift, bit 8 set 101010110_00000011101001 Xor 100010011 Result 001000101_00000011101001 Shift 010001010_0000011101001 Bit 8 set 100010100_000011101001 Xor 100010011 Result 000000111_000011101001 Shift 000001110_00011101001 000011100_0011101001 000111000_011101001 001110000_11101001 <- At this point all bits except the crc have been shifted (crc was E9 from specification paper) 011100001_1101001 in order to find the crc field value, shift 8 zeroes in Bit 8 set 111000011_101001 001110000_00000000 Xor 100010011 011100000_0000000 Result 011010000_101001 111000000_000000 Shift, bit 8 set 110100001_01001 100010011 Xor with poly Xor 100010011 011010011_000000 Result 010110010_01001 110100110_00000 Shift, bit 8 set 101100100_1001 100010011 Xor with poly Xor 100010011 010110101_00000 Result 001110111_1001 101101010_0000 Shift 011101111_001 100010011 Xor with poly Bit 8 set 111011110_01 001111001_0000 Xor 100010011 011110010_000 Result 011001101_01 111100100_00 Shift, bit 8 set 110011010_1 100010011 Xor with poly Xor 100010011 011110111_00 Result 010001001_1 111101110_0 Shift, bit 8 set 100010011 100010011 Xor with poly Xor 100010011 011111101_0 Result 000000000 111111010 All bits shifted, finished 100010011 Xor with poly 011101001 All bits shifted, crc field = %0_1110_1001 = $E9 The decode process can be summed up as: Loop: Shift bits left into crc_result Is bit 8 of crc_result set? Yes - xor crc_result with polynomial All bits shifted? No - continue looping Yes - finished, crc_result will be clear for a properly received message The encode process is just like the above, but it needs to loop for an additional eight bits (crc field length) }}I cannot for the life of me figure out how this problem works though, your answer was $14, the online calculator's
answer was $14 but I keep getting 100100 $24 or 1001000 $48 when I do it by hand and when I input those numbers into my calculator. Even when I try the wikipedia way, I still get 1001000, what am I doing wrong?
|--53--||--D2--| %0101001111010010 000000000_0101001111010010 start 000000000_101001111010010 shift the bitstream left until bit 8 of the working register is set 000000001_01001111010010 shift 000000010_1001111010010 shift 000000101_001111010010 shift 000001010_01111010010 shift 000010100_1111010010 shift 000101001_111010010 shift 001010011_11010010 shift 010100111_1010010 shift 101001111_010010 shift - bit 8 is set 101001111 100010011 xor with the polynomial: 100010011 001011100_010010 result = 001011100 101110001_0010 shift - bit 8 is set 100010011 xor 001100010_0010 result 110001000_10 shift - bit 8 is set 100010011 xor 010011011_10 result 100110111_0 shift - bit 8 is set 100010011 xor 000100100_0 result - all bits are shifted 001001000 shift - out of bitsWikipedia way
53D2 / 00010100 or $14 0101001111010010 00000000 <--- input right padded by 8 bits (n bits) 100010011 <--- divisor 001011100010010 00000000 100010011 0011000100010 00000000 100010011 01001101110 00000000 100010011 0001001000 00000000 ___________________ 1000100 11 0001100 11000000 1000 10011 0100 01011000 100 01000000 100 010011 000 000011 -------------------For the second code block, you somehow inserted an extra line:
53D2 / 00010100 or $14 0101001111010010 00000000 <--- input right padded by 8 bits (n bits) 100010011 <--- divisor 001011100010010 00000000 100010011 0011000100010 00000000 100010011 01001101110 00000000 100010011 0001001000 00000000 ___________________ 1000100 11 0001100 11000000 1000 10011 0100 01011000 100 01000000 <- where did this line come from? 100 010011 It should be the polynomial 000 000011 corrected version: ___________________ 1000100 11 0001100 11000000 1000 10011 0100 01011000 100 010011 000 00010100 <- $14