Κυριακή 20 Φεβρουαρίου 2022

How M2000 demonstrate algorithms: CRC-32 (cyclic redundancy check)

This tutorial shows how M2000 environment, using M2000 language, code a known algorithm, the crc -32 or cyclic redundancy check.

Also we see how this can be done faster using Api call, the RtlComputCrc32 function of ntdll. This function is a _stdCall (if we wish to call a c functions with _cdecl call we use lib c "..."). Here all parameters are IN (input) and the return value is a 32byte which "converted" to long, signed. This is how internal system supposed to use the number. But it is an unsigned long, 32 bit, so we handle it like this using Uint() which return a Currency type (which is internal 64bit singed integer, rendering to string as a value/1000, showing the least significant 4 digits as decimals, so 15 digits left of decimal point and 4 right the decimal point). If we want to pass a Unsiged long we use sint(), so sint(0XFFFFFFFF) return -1 long type, or 0xFFFFFFFF& which return -1 (but 0xFFFFFFFF return the unsinged value 4294967295), and sint(0xFFFF,2) return -1 long type which easily converted to integer (2 bytes). Also 0xFFFF& is long type 65535, same as 0xFFFF, and 0xFFFF% is -1 integer type.

All 32bit functions like binary.xor() return currency unsigned value from 0x0 ro 0xFFFFFFFF.

So CheckApi, is real easy to understand. We place in a Declare line the name of function CRC32, the library which the actual function exist, and the parameter list which we say which are Long type, which means any 32 byte value, as long signed value, and this include pointers also). We see a$ as input parameter, and this is a long pointer to first character. We have to place the nubper of bytes (which is always 2*len(a$) for any a$, including those who have ansi encoding, and maybe they have odd number of bytes, so a 3.5 length means, 35 words or 7 bytes).

Module checkApi are defined two times. The second time change the first module's definition. So in the second definition we split the string to two parts a$ and b$ and call first for the a$ and the result goes to second call for b$. This demonstrate that we can produce a crc from something we read in parts, without loading all in the memory.

The CheckIt module has an inner function which make a table (an array) and a lambda function which hold the calculated array to lambda closure. So the final crc32 is a variable and a function. As variable can be returned as value (including the closure). As function crc32 can invoke from expressions or using Call, and the closure crct act as local variable. A lambda function can call itself, using either the name of function (which maybe change, so isn't good for recursive call)  or the lambda() or lambda$() depends of major type of return value, and for each call the closures are like global (but is local), the same for each inner call. Here we don't have recursion.

Buffer bur is memory defined in heap, where buf(0) is the real memory address. Real memory addresses needed for passing arrays to external libraries. Here we want only to place the string and just change the indexing to byte boundary, which means each index point to specific byte, starting from 0 (strings  characters starting from 1). The Len() function works for strings and other types, like buffers/  For buffers the return value is the same type as the basic type of buffer, here is the byte (can be byte, integer, long, single, double or a specific Structure which defined in previous steps)

Literal numbers such as 2, 1, -1 are double type (not long). OxFFFFFFFF is currency, 0x0 is currency too. See in crc32(0, a$, len(a$)*2) we pass double, string, double and interpreter convert them to three longs, the second one  a pointer to first string byte. Overflows through exceptions, but we can handle them in Try ok { } blocks, otherwise the module terminate execution and we get the error message (using shift f1 we open editor where the problem occur, most time that works immediately after the error happen)


Module CheckApi {
      Declare CRC32 LIB c "ntdll.RtlComputeCrc32" {Long Zero, a$, long s}
      a$=Str$("The quick brown fox jumps over the lazy dog")
      // a len of 3.5 is 7 bytes. Len is a double which return number of words
      // so a 0.5 word is a byte
      // because we get a long (singed) we convert it to unsigned 32 bit (using same bits)
      Hex Uint(CRC32(sint(0x0),a$,len(a$)*2))
}
CheckApi
Module CheckApi {
      Declare CRC32 LIB "ntdll.RtlComputeCrc32" {Long Zero, a$, long s}
      a$=Str$("The quick brown fox")
      b$=Str$(" jumps over the lazy dog")
      Hex Uint(CRC32(CRC32(0,a$,len(a$)*2),b$,len(b$)*2))
}
CheckApi
Module CheckIt {
Function PrepareTable {
Dim Base 0, table(256)
For i = 0 To 255
k = i
For j = 0 To 7
If binary.and(k,1)=1 Then
k =binary.Xor(binary.shift(k, -1) , 0xEDB88320)
Else
k=binary.shift(k, -1)
End If
Next
table(i) = k
Next
=table()
}
crc32= lambda ' we can break the lambda definition in parts
crct()=PrepareTable() ' this is a closure
(buf$) ' this is the input paremeter
-> { ' this is the function body of lambda
if len(buf$) Else exit
// we make a buffer of bytes and place string there
// Eval(buf, 0) read the first byte as unsigned number (0 to 255)
// buf and buf$ can coexist, they are different variables
buffer buf as byte*len(buf$)*2
return buf, 0:=buf$
crc =0xFFFFFFFF
For i = 0 To Len(buf) -1
crc = binary.xor(binary.shift(crc, -8), crct(binary.xor(binary.and(crc, 0xff), Eval(buf, i))))
Next
=0xFFFFFFFF-crc
}
// str$() convert Utf16LE to ANSI 8bit
// Hex is like Print but conver unsigned numbers to hex
Hex crc32(str$("The quick brown fox jumps over the lazy dog")) ' return 0x414fa339
}
CheckIt

Module CheckIt {

	Function PrepareTable {
Dim Base 0, table(256)
For i = 0 To 255
k = i
For j = 0 To 7
If binary.and(k,1)=1 Then
k =binary.Xor(binary.shift(k, -1) , 0xEDB88320)
Else
k=binary.shift(k, -1)
End If
Next
table(i) = k
Next
=table()
}
crc32= lambda ' we can break the lambda definition in parts
crct()=PrepareTable() ' this is a closure
(crc, buf$) ' this is the input paremeter
-> { ' this is the function body of lambda
if len(buf$) Else exit
// we make a buffer of bytes and place string there
// Eval(buf, 0) read the first byte as unsigned number (0 to 255)
// buf and buf$ can coexist, they are different variables
buffer buf as byte*len(buf$)*2
return buf, 0:=buf$
crc =0xFFFFFFFF-crc
For i = 0 To Len(buf) -1
crc = binary.xor(binary.shift(crc, -8), crct(binary.xor(binary.and(crc, 0xff), Eval(buf, i))))
Next
=0xFFFFFFFF-crc
}
// str$() convert Utf16LE to ANSI 8bit
// Hex is like Print but conver unsigned numbers to hex
Hex crc32(0@, Str$("The quick brown fox jumps over the lazy dog")) ' return 0x414fa339
Hex crc32(crc32(0@, str$("The quick brown fox")), str$(" jumps over the lazy dog")) ' return 0x414fa339
}
CheckIt

Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου