CRCs (as applied to serial data streams) lazarus / 21-General ---------------------------------------------------------------------- MarkMLl · 2021-10-30 19:47 I wonder if I could ask a general question. I've put together a nice little library which can read lots of different primitive data types (distinguished by size, endianness, signed/unsigned and so on). It also has a facility to backtrack any number of bytes, I was envisaging use with parsers etc. It would obviously be trivially easy to extent the GetXXX() functions to accumulate a CRC, but I'm hesitant about backtracking in this situation. Considering the fairly-standard CRCs of up to 32 bits, can I assume that if the incoming data is being processed one byte at a time that no more than one byte of data is potentially lost per round? Or since most if not all of them have a single-bit shl/shr per round can I assume one bit per round? I'm obviously aware of the fact that even if 16 or 32 bits needed to be saved per round to enable backtracking the storage required would be negligible by today's standards. I'm just trying to get a grip on the issues. MarkMLl ---------------------------------------------------------------------- MarkMLl · 2021-10-31 08:21 @Jamie: wrong. A CRC can be calculated entirely correctly on a byte- by-byte basis... how the hell do you think that classical hardware support based on a shift register did it? MarkMLl ---------------------------------------------------------------------- alpine · 2021-10-31 08:38 Quote from: MarkMLl on October 30, 2021, 09:47:44 pmI wonder if I could ask a general question. I've put together a nice little library which can read lots of different primitive data types (distinguished by size, endianness, signed/unsigned and so on). It also has a facility to backtrack any number of bytes, I was envisaging use with parsers etc. It would obviously be trivially easy to extent the GetXXX() functions to accumulate a CRC, but I'm hesitant about backtracking in this situation. But what you want to achieve by this backtracking? The backtracking on the data stream to be done together with un-doing the CRC back to the point? ---------------------------------------------------------------------- MarkMLl · 2021-10-31 08:58 Quote from: y.ivanov on October 31, 2021, 09:38:25 amBut what you want to achieve by this backtracking? The backtracking on the data stream to be done together with un-doing the CRC back to the point? The scenario is that I'm reading serial (as in serial comms, i.e. not seekable) data and processing using something like recursive descent or possibly a bidding mechanism. So instead of reading a byte and saying "This indicates that what follows should be passed to this function", I want to be able to allow a function to read an arbitrary amount of data before it decides that there's something there it isn't qualified to handle at which point it backtracks and returns failure. I've used that technique on fairly complex files before now, where the backtracking can obviously be accomplished by a seek. A serial stream is obviously more problematic, I've been decoding data from a logic analyser over the last few days and there were a small number of places where the backtracking was definitely useful. I've also had to implement "read but don't consume" facilities in other comms handling in the past, and a backtrack is obviously equivalent. In practice I think it would be reasonable to restrict the backtracking to 4K because of the Linux kernel issue I mentioned in another thread, and while there are obviously plenty of protocols around which use blocks larger than that I don't recall any which put important contextual information /after/ a block of data of arbitrary size (unless of course you want to consider DLE unstuffing as a kind of backtracking). And a 4K limit, on a modern computer, would imply that even a 32-bit CRC could have every generated value stored rather than having to reach into the CRC generators and catch the shift loss. MarkMLl ---------------------------------------------------------------------- alpine · 2021-10-31 10:03 Quote from: MarkMLl on October 31, 2021, 09:58:19 amQuote from: y.ivanov on October 31, 2021, 09:38:25 amBut what you want to achieve by this backtracking? The backtracking on the data stream to be done together with un-doing the CRC back to the point? The scenario is that I'm reading serial (as in serial comms, i.e. not seekable) data and processing using something like recursive descent or possibly a bidding mechanism. So instead of reading a byte and saying "This indicates that what follows should be passed to this function", I want to be able to allow a function to read an arbitrary amount of data before it decides that there's something there it isn't qualified to handle at which point it backtracks and returns failure. Considering you have enough RAM, can't you just organize the reading primitives to buffer the input until that function returns success or failure and then discards that buffer when consumed or reuses it in case of backtracking? Quote from: MarkMLl on October 31, 2021, 09:58:19 amI've used that technique on fairly complex files before now, where the backtracking can obviously be accomplished by a seek. A serial stream is obviously more problematic, I've been decoding data from a logic analyser over the last few days and there were a small number of places where the backtracking was definitely useful. I've also had to implement "read but don't consume" facilities in other comms handling in the past, and a backtrack is obviously equivalent. In practice I think it would be reasonable to restrict the backtracking to 4K because of the Linux kernel issue I mentioned in another thread, and while there are obviously plenty of protocols around which use blocks larger than that I don't recall any which put important contextual information /after/ a block of data of arbitrary size (unless of course you want to consider DLE unstuffing as a kind of backtracking). What is that kernel issue? Why it is related to the backtracking size?  Quote from: MarkMLl on October 31, 2021, 09:58:19 amAnd a 4K limit, on a modern computer, would imply that even a 32-bit CRC could have every generated value stored rather than having to reach into the CRC generators and catch the shift loss. MarkMLl I don't see why to store the CRC accum. for each byte considering the low cost of the CRC calculation. In the discard/reuse I'd proposed, the CRC calculation can be just postponed until the parsing function returns success and the buffer should be discarded, i.e. the data is consumed. Edit: But why you should backtrack the CRC anyway? Isn't it data already received? ---------------------------------------------------------------------- MarkMLl · 2021-10-31 11:10 Quote from: y.ivanov on October 31, 2021, 11:03:05 amWhat is that kernel issue? Why it is related to the backtracking size?  https://forum.lazarus.freepascal.org/index.php/topic,56639.msg420970.h tml#msg420970 Strictly, that only limits the situation when I need to check whether backtrack+available >= required. QuoteEdit: But why you should backtrack the CRC anyway? Isn't it data already received? The CRC is typically application-defined. and this is dealing with data as it arrives on (e.g.) a serial line and does not necessarily have a predefined length. Hence it really needs to be defined locally. MarkMLl ---------------------------------------------------------------------- alpine · 2021-10-31 12:37 Quote from: MarkMLl on October 31, 2021, 12:10:34 pmQuote from: y.ivanov on October 31, 2021, 11:03:05 amWhat is that kernel issue? Why it is related to the backtracking size?  https://forum.lazarus.freepascal.org/index.php/topic,56639.msg420970.h tml#msg420970 Strictly, that only limits the situation when I need to check whether backtrack+available >= required. Why you'd not use an additional internal buffer, presumably with a bigger size than 4K? Quote from: MarkMLl on October 31, 2021, 12:10:34 pmQuoteEdit: But why you should backtrack the CRC anyway? Isn't it data already received? The CRC is typically application-defined. and this is dealing with data as it arrives on (e.g.) a serial line and does not necessarily have a predefined length. Hence it really needs to be defined locally. MarkMLl I presume the CRC definition is not to be changed during a single transmission, i.e. at the times of the backtaracking. I still can't get the point for keeping all intermediate accumulator values ... IMO even in the case of backtrack, the previous data should be considered again by alternate parsing function, but the data  de facto has already been received (i.e. sent by other party) and will not change ... unless you have some means  to request it again. ---------------------------------------------------------------------- MarkMLl · 2021-10-31 13:50 Quote from: y.ivanov on October 31, 2021, 01:37:22 pmWhy you'd not use an additional internal buffer, presumably with a bigger size than 4K? Well, it's just not how I did it :-) In fairness, I only discovered the "feature" during testing after I'd written the rest of the code, and in practice it only affects a small number of functions (specifically, read a fixed number of bytes and read a length-prefixed string where the length is >8 bits big- or little-endian) and I didn't feel like redoing too much since everything else worked well. I think that if I had to argue the point I'd say that I was avoiding pulling stuff from the line so as to be able to preserve the timing information, things can get seriously weird when one is forced to do too much of that and I'd rather not complicate the situation any further. There is also the possibility on unix-style systems of wanting to behave like a getty and hand control to some other program. And so on :-) QuoteI presume the CRC definition is not to be changed during a single transmission, i.e. at the times of the backtaracking. I still can't get the point for keeping all intermediate accumulator values ... IMO even in the case of backtrack, the previous data should be considered again by alternate parsing function, but the data  de facto has already been received (i.e. sent by other party) and will not change ... unless you have some means  to request it again. I'd rather not presume that, and I've also been in a position before now where I needed to apply multiple CRC algorithms... although in that particular case I was able to do it to already-received data (this was serial comms monitoring, where I was able to both test against multiple CRCs and to slide both ends of the area tested to look for matches... worked nicely). So the situation I envisaged was more one of giving the existing functions hooks by which they can submit an incoming byte to an indeterminate number of CRC algorithms, and my specific question related to how much state each of those functions would need to retain (e.g. one bit per round). And I'd /definitely/ not like to assume that whatever was at the far end would know about retransmitting data, and that I was in a position to request that (again, I might be parsing data captured passively from a comms session). I'd emphasise that I'm not talking anything "black hat" here, but I've fairly often been in the position of having to look at "alien" equipment that's appeared on a comms line which should have been reserved for us. Serial comms is nice clean fun :-) MarkMLl ---------------------------------------------------------------------- alpine · 2021-10-31 15:45 Quote from: MarkMLl on October 31, 2021, 02:50:20 pm*snip* I think that if I had to argue the point I'd say that I was avoiding pulling stuff from the line so as to be able to preserve the timing information, things can get seriously weird when one is forced to do too much of that and I'd rather not complicate the situation any further. There is also the possibility on unix-style systems of wanting to behave like a getty and hand control to some other program. And so on :-) But in case you need the timings, you won't have other way than reading at the fastest speed possible while saving the timing information along with the data ... AFAIK OS buffers don't keep such an information. Quote from: MarkMLl on October 31, 2021, 02:50:20 pm*snip* *snip* I'd rather not presume that, and I've also been in a position before now where I needed to apply multiple CRC algorithms... although in that particular case I was able to do it to already-received data (this was serial comms monitoring, where I was able to both test against multiple CRCs and to slide both ends of the area tested to look for matches... worked nicely). So the situation I envisaged was more one of giving the existing functions hooks by which they can submit an incoming byte to an indeterminate number of CRC algorithms, and my specific question related to how much state each of those functions would need to retain (e.g. one bit per round). In that complex case I would make some checkpoint saving methods over the internal buffer, something like mark/retain/rollback, with the hooks obliged to save/update/restore the algorithms state (accumulators?) at the certain positions related to the backtracking ... anyway, you're not going to go back byte by byte, wouldn't you? BTW, my abstract algebra knowledge was left behind somewhere at the end of the past century and I would not dare to implement (or give an advice to) any advanced backwards polynomial calculations or like. Quote from: MarkMLl on October 31, 2021, 02:50:20 pmAnd I'd /definitely/ not like to assume that whatever was at the far end would know about retransmitting data, and that I was in a position to request that (again, I might be parsing data captured passively from a comms session). I'd emphasise that I'm not talking anything "black hat" here, but I've fairly often been in the position of having to look at "alien" equipment that's appeared on a comms line which should have been reserved for us. Given the unknowns, including invading alien equipment,  there is hardly much more to say than it is very likely that the numerous line contentions will probably render your CRC matching useless. But what's left is the pure fun of doing it ;) ---------------------------------------------------------------------- MarkMLl · 2021-10-31 16:18 Quote from: y.ivanov on October 31, 2021, 04:45:49 pmBut in case you need the timings, you won't have other way than reading at the fastest speed possible while saving the timing information along with the data ... AFAIK OS buffers don't keep such an information. Correct. QuoteIn that complex case I would make some checkpoint saving methods over the internal buffer, something like mark/retain/rollback, with the hooks obliged to save/update/restore the algorithms state (accumulators?) at the certain positions related to the backtracking ... anyway, you're not going to go back byte by byte, wouldn't you? Yes, byte-by-byte is entirely possible. Standard recursive-descent stuff. Also I found myself handling a 7-byte big-endian timestamp by reading a qword and putting one byte back. QuoteBTW, my abstract algebra knowledge was left behind somewhere at the end of the past century and I would not dare to implement (or give an advice to) any advanced backwards polynomial calculations or like. It's quite simple if you're doing it using a precomputed table: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i FUNCTION comp16(VAR table: table16; current: INTEGER; value: BYTE): INTEGER; (* Compute a "classic" 16-bit CRC using Campbell's crcupdate()          *)(* algorithm and the specified table.                                 *) (* Transcribed from crc.mod.                                          *) BEGIN  comp16:= (current SHL 8) XOR table[((current SHR 8) XOR INTEGER(value)) AND $00FF]END { comp16 } ;  FUNCTION CrcCcitt(current: INTEGER; value: BYTE): INTEGER; BEGIN  IF tableCcitt = NIL THEN BEGIN    NEW(tableCcitt);    init16(tableCcitt^, PolyCcitt)  END;  CrcCcitt:= comp16(tableCcitt^, current, value)END { CrcCcitt } ;  ...so there's basically one bit lost per incoming byte. Whether it's actually worth storing the lost bits in packed form is moot. QuoteGiven the unknowns, including invading alien equipment,  there is hardly much more to say than it is very likely that the numerous line contentions will probably render your CRC matching useless. But what's left is the pure fun of doing it I /definitely/ didn't say invading. But very often one needs to say- as an example- "Is this SLIP?" or "Is this PPP?" and at that point knowing the CRCs in play is important. MarkMLl ---------------------------------------------------------------------- alpine · 2021-10-31 20:31 Quote from: MarkMLl on October 31, 2021, 05:18:33 pm*snip* QuoteIn that complex case I would make some checkpoint saving methods over the internal buffer, something like mark/retain/rollback, with the hooks obliged to save/update/restore the algorithms state (accumulators?) at the certain positions related to the backtracking ... anyway, you're not going to go back byte by byte, wouldn't you? Yes, byte-by-byte is entirely possible. Standard recursive-descent stuff. Also I found myself handling a 7-byte big-endian timestamp by reading a qword and putting one byte back. [/code] Wouldn't be your life much easier if you read dword, word, and byte? Quote from: MarkMLl on October 31, 2021, 05:18:33 pmQuoteBTW, my abstract algebra knowledge was left behind somewhere at the end of the past century and I would not dare to implement (or give an advice to) any advanced backwards polynomial calculations or like. It's quite simple if you're doing it using a precomputed table: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {Here goes sample using Sarwate algorithm (single lookup table) }... It is quite simple in code, but there is complicated abstract algebra theory behind it. So I said I wouldn't dare to try to undo the last "round" or "rounds" mainly because I don't know how to do it or is it possible.  Quote from: MarkMLl on October 31, 2021, 05:18:33 pm...so there's basically one bit lost per incoming byte. Whether it's actually worth storing the lost bits in packed form is moot. I don't understand this part at all. In each incoming byte there are 8 coefficients of the dividend polynomial (being either zero or one) and I can't get your point when you say "...so there's basically one bit lost per incoming byte". One bit lost where? One bit (coefficient) different and the CRC will just go haywire (different table entry) and that is the whole idea of it. Quote from: MarkMLl on October 31, 2021, 05:18:33 pmQuoteGiven the unknowns, including invading alien equipment,  there is hardly much more to say than it is very likely that the numerous line contentions will probably render your CRC matching useless. But what's left is the pure fun of doing it I /definitely/ didn't say invading. But very often one needs to say- as an example- "Is this SLIP?" or "Is this PPP?" and at that point knowing the CRCs in play is important. "Invading aliens" was a sort of clumsy humor. You should really tell what are you doing otherwise it's all just a guessing and chatting. ---------------------------------------------------------------------- MarkMLl · 2021-10-31 21:20 Quote from: y.ivanov on October 31, 2021, 09:31:32 pmQuote from: MarkMLl on October 31, 2021, 05:18:33 pmAlso I found myself handling a 7-byte big-endian timestamp by reading a qword and putting one byte back. Wouldn't be your life much easier if you read dword, word, and byte? Maybe, but the spec said there was a 7-byte timestamp followed by more stuff. At that point I didn't want to know that /part/ of it was available, I wanted to know that /all/ of it was available for error reporting etc. QuoteIt is quite simple in code, but there is complicated abstract algebra theory behind it. So I said I wouldn't dare to try to undo the last "round" or "rounds" mainly because I don't know how to do it or is it possible.  True... and my knowledge of Galois Fields is limited to knowing that they aren't some sort of dessert pancake :-) QuoteI don't understand this part at all. In each incoming byte there are 8 coefficients of the dividend polynomial (being either zero or one) and I can't get your point when you say "...so there's basically one bit lost per incoming byte". One bit lost where? One bit (coefficient) different and the CRC will just go haywire (different table entry) and that is the whole idea of it. Yes, you're right and many thanks. That's the consequence of my glancing over code and focussing on the assembler instruction SHL (etc.) rather than on the fact that it's an operator with 8 as the number of bits to be shifted. Quote"Invading aliens" was a sort of clumsy humor. You should really tell what are you doing otherwise it's all just a guessing and chatting. Sorry. I just have... reasons... that I can't afford to be accused of anything "black-hat". MarkMLl ---------------------------------------------------------------------- alpine · 2021-11-01 11:09 Quote from: MarkMLl on October 31, 2021, 10:20:59 pm*snip* Yes, you're right and many thanks. That's the consequence of my glancing over code and focussing on the assembler instruction SHL (etc.) rather than on the fact that it's an operator with 8 as the number of bits to be shifted. Glad to be helpful. It must be kind of hyper-focus, I'm sure you know what LFSR is (noted somewhere above). ---------------------------------------------------------------------- MarkMLl · 2021-11-01 12:09 Quote from: y.ivanov on November 01, 2021, 12:09:51 pmQuote from: MarkMLl on October 31, 2021, 10:20:59 pm*snip* Yes, you're right and many thanks. That's the consequence of my glancing over code and focussing on the assembler instruction SHL (etc.) rather than on the fact that it's an operator with 8 as the number of bits to be shifted. Glad to be helpful. It must be kind of hyper-focus, I'm sure you know what LFSR is (noted somewhere above). Oh, you asked about why I was doing this etc. More than anything else it's just a distillation of stuff I've needed in the past, but it was brought to the front of my mind by wanting to capture data (in standard VCD format) from my ageing HP logic analyser which is connected via an HP-IB adapter that looks like a serial port. This is predominantly big-endian, but produces a data stream with lots of different fundamental types, which I can now read with appropriate timeouts both before and between the individual bytes. However I've not been paying particular attention to error checking (in fact I've not even bothered to work out which CRC is being used), and the fact that blocks are variable-length and not necessarily being parsed by a single function implies that the best that can be done is accumulating a running value and checking when appropriate. Which is obviously complicated by backtracking, but all in all the facilities are useful. MarkMLl