Print Page - Help needed with checksums

Programming => Problems & Solutions => Topic started by: Arnold on January 30, 2019, 05:07:26 AM

Title: Help needed with checksums
Post by: Arnold on January 30, 2019, 05:07:26 AM

Hello,

can someone help with my logical error? Exploring the examples in Rosettacode for the CRC-32 algorithm, I found a solution using the WinApi function RtlComputeCrc32, which seems to be undocumented. I also found definitons of RtlCrc32, RtlCrc64 in Winnt.h.

Charles has already generated the crc32 checksum in assembler.

The RtlComputeCrc32 function works for me, but I do something wrong with RtlCrc32. I assume I have to apply a special value for InitialCrc, but I have no idea how I can derive this value. Or do I something else wrong?

Roland

Code: [Select]

$ filename "Checksums.exe"  

'uses rtl32
'uses rtl64

uses console

'RtlComputeCrc32 (DWORD dwInitial, const BYTE *pData, INT iLen)  result dword
'RtlCrc32 ( void const* Buffer, size_t Size, DWORD InitialCrc )  result dword
'RtlCrc64 ( void const* Buffer, size_t Size, ULONGLONG InitialCrc ) result ulonglong

string fname="Checksums.o2bas"
string s
getfile fname, s

extern lib "ntdll.dll"
! RtlComputeCrc32
! RtlCrc32
! RtlCrc64
end extern

printl hex (RtlComputeCrc32 0, s, len s)
printl right(hex (RtlComputeCrc32 0, s, len(s), 8))
printl

printl hex (RtlCrc32 s, len(s), 0) ": Incorrect."


printl "Enter..."
waitkey

Title: Re: Help needed with checksums
Post by: Charles Pegge on January 30, 2019, 09:10:47 AM

Hi Roland,

I can't make sense of RTLCRC32 either.

We have a CRC32 function in inc\chaos.inc.

uses chaos
int a = Crc32(strptr s, len s)

Title: Re: Help needed with checksums
Post by: Mike Lobanovsky on January 30, 2019, 12:57:54 PM

If we're talking about computing/verifying the check sum of a disk image of PE executable file, then make use of MapFileAndCheckSum (https://docs.microsoft.com/en-us/windows/desktop/api/imagehlp/nf-imagehlp-mapfileandchecksuma) WinAPI.

It can read the CRC-32 value written into the PE header and simultaneously recalculate its actual value again omitting the four bytes that the PE header reserves for writing the checksum value into.

OTOH if you want to calc an MS-compatible CRC-32 for an arbitrary sequence of bytes in memory or on disk, you can use the following C code (or its O2 equivalent) as it was used in the FBSL sources to implement its CheckSum keyword:

Code: C

// CRC calc forward declarations
ULONG   crc32_table[256]; // Lookup table array
void    Init_CRC32_Table(void);
ULONG   Reflect(ULONG ref, char ch);
 
 
// Main function
unsigned long CheckSum(char* data, int dataLen)
{
        if (crc32_table[1] == 0) Init_CRC32_Table(); // ML 23.09.2012: do table init once
 
        // Be sure to use unsigned variables,
        // because negative values introduce high bits
        // where zero bits are required.
 
        // Start out with all bits set high.
        unsigned long ulCRC = 0xffffffff;
        unsigned char *buffer;
 
        // Save the text in the buffer.
        buffer = (unsigned char *)data;
        // Perform the algorithm on each character
        // in the string, using the lookup table values.
        while (dataLen--)
                ulCRC = (ulCRC >> 8) ^ crc32_table[(ulCRC & 0xFF) ^ *buffer++];
        // Exclusive OR the result with the beginning value.
        return ulCRC ^ 0xffffffff;
}
 
// Utility functions
 
// Call this function only once to initialize the CRC table.
void Init_CRC32_Table(void)
{
        // This is the official polynomial used by CRC-32
        // in PKZip, WinZip and Ethernet.
        unsigned long ulPolynomial = 0x04c11db7;
 
        // 256 values representing ASCII character codes.
        register int i;
        for (i = 0; i <= 0xFF; i++) {
                crc32_table[i] = Reflect(i, 8) << 24;
                register int j;
                for (j = 0; j < 8; j++)
                        crc32_table[i] = (crc32_table[i] << 1) ^ (crc32_table[i] & (1 << 31) ? ulPolynomial : 0);
                crc32_table[i] = Reflect(crc32_table[i], 32);
        }
}
 
// Reflection is a requirement for the official CRC-32 standard.
// You can create CRCs without it, but they won't conform to the standard.
ULONG Reflect(ULONG ref, char ch)
{       // Used only by Init_CRC32_Table()
 
        unsigned long value = 0;
 
        // Swap bit 0 for bit 7
        // bit 1 for bit 6, etc.
        register int i;
        for (i = 1; i < (ch + 1); i++) {
                if (ref & 1)
                        value |= 1 << (ch - i);
                ref >>= 1;
        }
 
        return value;
}

Title: Re: Help needed with checksums
Post by: Arnold on January 31, 2019, 03:37:15 AM

Hi Mike,

thank you for your comments. Your Checksum function uses the same polynomial as the asm code of \inc\chaos.inc and I tried to port the code to Oxygen:

Code: [Select]

'Ported from FBSL C-code (Mike Lobanowsky)
$ filename "CheckSumCRC32.exe"

'uses rtl32
'uses rtl64

uses console

ulong crc32_table[256]  ' Lookup table array

' Utility functions

function Reflect(uint ref, byte ch) as uint
   ' Used only by Init_CRC32_Table()
    uint value = 0
 
   ' Swap bit 0 for bit 7
   ' bit 1 for bit 6, etc.
   int i
   for i = 1 to ch + 1
      if (ref and 1) then value = value or 1 << (ch - i)
      ref = ref >> 1
   next i
 
   return value
end function
 
' Call this function only once to initialize the CRC table.
sub Init_CRC32_Table()
   ' This is the official polynomial used by CRC-32
   ' in PKZip, WinZip and Ethernet.
   uint ulPolynomial = 0x04c11db7
 
   ' 256 values representing ASCII character codes.
   int i
   for i = 0 to 0xFF
      crc32_table[i] = Reflect(i, 8) << 24
      int j
      for j = 0 to 7
         uint mask = crc32_table[i] and (1 << 31)
         if mask then
           crc32_table[i] = (crc32_table[i] << 1) xor ulPolynomial
         else
           crc32_table[i] = (crc32_table[i] << 1) xor 0
         end if 
      next j    
      crc32_table[i] = Reflect(crc32_table[i], 32)      
   next i
end sub

' Main function
function CheckSum(string buffer) as uint
   if (crc32_table[1] == 0) then Init_CRC32_Table() ' do table init once
 
   ' Be sure to use unsigned variables,
   ' because negative values introduce high bits
   ' where zero bits are required.
 
   ' Start out with all bits set high.
   uint ulCRC = 0xffffffff

   ' Perform the algorithm on each character
   ' in the string, using the lookup table values.
   int datalen=len(buffer)
   int ix=1
   while dataLen
      dataLen -= 1
      'older oxygen.dll
      'int idx = (ulCRC and 0xFF) xor asc(mid(buffer,ix,1))
      'ulCRC = (ulCRC >> 8) xor crc32_table[idx]      
      'newer oxygen.dll
      ulCRC = (ulCRC >> 8) xor crc32_table[(ulCRC and 0xFF) xor asc(mid(buffer,ix,1))]
      ix+=1
   wend
   ' Exclusive OR the result with the beginning value.
   return ulCRC xor 0xffffffff
end function


' ------ main ------

string s = "The quick brown fox jumps over the lazy dog"
printl "Text = " s
printl "The CRC-32 checksum = " right (hex(CheckSum(s)),8)   '414FA339

string fname= "CheckSumCRC32.o2bas"
getfile fname, s
printl
printl "Filename = " fname
printl "The CRC-32 checksum = " right (hex(CheckSum(s)),8)

printl "Enter ..."
waitkey

I also tried to apply the algorithm found at Rossettacode (using a different polynomial) which is derived from W3C:

Code: [Select]

'https://www.w3.org/TR/PNG/#D-CRCAppendix
$ filename "CheckCRC32.exe"

'uses rtl32
'uses rtl64

uses console

function crc32(string buf) as uint
   indexbase 0

   static uint crc_table[256]
   static uint crc_table_computed
   uint crc
   int n, k

   if crc_table_computed = 0 then
     for n = 0 to 255
        crc = n
        for k = 0 to 7
           if (crc and 1) then crc = (crc >> 1) xor 0xedb88320 else crc = crc >> 1
           crc_table[n] = crc
        next k
     next n
     crc_table_computed = 1
   end if

   crc = 0xffffffff
    
   for n = 1 to len(buf)
      'older oxygen.dll
      'int idx = (crc and 0xff) xor asc(mid(buf,n,1)))
      'crc = (crc >> 8) xor crc_table[idx]
      'newer oxygen.dll        
      crc = (crc >> 8) xor crc_table[(crc and 0xff) xor asc(mid(buf,n,1))]
   next

   return not crc
end function


' ------ main ------

string s = "The quick brown fox jumps over the lazy dog"
printl "Text = " s
printl "The CRC-32 checksum = " right (hex(crc32(s)),8)   '414FA339

string fname= "CheckCRC32.o2bas"
getfile fname, s
printl
printl "Filename = " fname
printl "The CRC-32 checksum = " right (hex(crc32(s)),8)
printl "Enter..."
waitkey

The code of the two examples works correctly only with oxygen.dll of OXSC19 path, especially when creating exe files. It is interesting to compare the different solutions. The asc(mid(buf,n,1)) expression could be optimized, but I wanted to use a simple way.

The MapFileAndCheckSum function is new to me but it is very interesting. I will do my next experiments with it.

Roland

Title: Re: Help needed with checksums
Post by: Mike Lobanovsky on January 31, 2019, 02:37:13 PM

Hi Roland,

Quote

... especially when creating exe files.

I'm not sure what you're up to but if what you're in fact trying to do is verify or calculate the checksum of an exe or dll file on disk or in memory, you aren't going to succeed with either of the two (or a zillion) implementations or polynomials. The four bytes that are reserved for storing the resultant crc itself are deep inside the PE header that's in itself also part of the calc. They cannot be so easily bypassed in the calc which is affected by both the byte values as well as the number of bytes involved in the calculation.

In such cases prefer at all times to use the MapFileAndCheckSum API that never fails and conforms to the PE loader expectations. Its only drawback is that it needs the exe or dll file to be dumped on disk first because it cannot read its memory image.

Title: Re: Help needed with checksums
Post by: Arnold on February 01, 2019, 01:54:17 AM

Hi Mike,

these are only experiments to explore the behaviour of the different versions of oxygen.dll. In Windows 10 I can use a right-click on a file in the Explorer to get all kind of CRC SHA checksums. So these code snippets are not really valuable for any purpose except perhaps for learning. Somehow I regret that there is so much knowledge that I have missed.

Roland

Title: Re: Help needed with checksums
Post by: Charles Pegge on February 01, 2019, 02:22:35 AM

Hi Mike and Roland,

o2 currently leaves the Checksum field null. But I can add this utility after the filing stage:

Code: [Select]

'PE FILE CRC STAMP
'https://docs.microsoft.com/en-us/windows/desktop/api/imagehlp/nf-imagehlp-mapfileandchecksuma
! MapFileAndCheckSumA lib "Imagehlp.dll"
dword e,i,o
e=MapFileAndCheckSumA("oxygen.dll",@i,@o)
select e
  case 2 : print "Could not map the file"
  case 3 : print "Could not map a view of the file"
  case 1 : print "Could not open the file"
  case 4 : print "Could not convert the file name to Unicode"
  case else : print hex(i) "   " hex(o) "    " e
end select

Title: Re: Help needed with checksums
Post by: Arnold on February 01, 2019, 05:35:01 AM

Hi Charles,

I did some tests with your routine. The dlls in system32 show values for HeaderSum and CheckSum. Files e.g. created with masm32 show only CheckSum. Files created with Freebasic show HeaderSum and CheckSum. Oxygen.dll e.g. in OXSC19 show only CheckSum. Older versions of oxygen.dll which you provided uncompressed with UPX show HeaderSum and CheckSum. The results do not allow a clear conclusion. The documentation of MSDN recommends that all images have valid checksums. So perhaps it does not hurt to provide a checksum? Without Mike, I would not even have known that this is possible.

Roland

Title: Re: Help needed with checksums
Post by: Mike Lobanovsky on February 01, 2019, 05:37:18 AM

Hi Charles and Roland,

Strictly speaking, the PE header crc field absolutely must be filled in only for the so called "native" executables, i.e. predominantly kernel mode drivers. Otherwise the PE loader will refuse to launch them if their crc's are missing or incorrect, being at the same time liberal enough with user mode executables.

OTOH problematic values in the PE header are often one (among many) of the causes why AV's would throw false alarms. So it'd better be filled in correctly. All MS compilers compute and store the checksums in the exe/dll/sys headers regardless of whether the binary is a kernel or user mode executable.

Note re. Charles' snippet:

The MapFileAndCheckSum API does not fill in the crc field for you. You have to do it yourself using the newly computed value that the API returns.

Title: Re: Help needed with checksums
Post by: Charles Pegge on February 02, 2019, 01:06:32 AM

This page shows how the checksum is calculated:

https://bytepointer.com/resources/microsoft_pe_checksum_algo_distilled.htm

This is a simple map of the PE headers:

http://www.sunshine2k.de/reversing/tuts/tut_pe.htm

...

The crc field must be set to 0 first.

Title: Re: Help needed with checksums
Post by: Charles Pegge on February 02, 2019, 02:07:01 AM

Here is the algorithm translated:

I have decomposed it into elementary steps.

Code: [Select]

'MapFileAndCheckSumA
'https://docs.microsoft.com/en-us/windows/desktop/api/imagehlp/nf-imagehlp-mapfileandchecksuma
'http://www.sunshine2k.de/reversing/tuts/tut_pe.htm
'https://www.codeproject.com/Articles/19326/An-Analysis-of-the-Windows-PE-Checksum-Algorithm
'https://bytepointer.com/resources/microsoft_pe_checksum_algo_distilled.htm
'
! MapFileAndCheckSumA lib "Imagehlp.dll"
'
string fi
string s
fi="oxygen.dll"
getfile fi,s
'
int *ck 'checksum
dword b at strptr(s)+60 'PE header offset
@ck=strptr(s)+b+0x58 'checksum location
'
'CLEAR CHECKSUM
ck=0
'
'CALCULATE CHECKSUM
uint uw  'upper word
uint ls  'byte length of data
uint ca  'checksum accumulator
word *pd 'input
int j    'iterator
ls=len(s)
@pd=strptr(s)
for j=1 to ls step 2 'each word
  ca+=pd
  uw=ca>>16
  ca and=0xffff
  ca+=uw
  @pd+=2
next
'final
uw=ca>>16
ca=uw+ca
ca and= 0xffff
ca+=ls 'add in byte length of data
'print hex(ca)
'
'SET CHECKSUM
ck=ca
putfile fi,s


'VERIFY
=======

dword e ' error
dword i ' previous checksum
dword o ' new checksum
'
e=MapFileAndCheckSumA("oxygen.dll",@i,@o)
select e
  case 2 : print "Could not map the file"
  case 3 : print "Could not map a view of the file"
  case 1 : print "Could not open the file"
  case 4 : print "Could not convert the file name to Unicode"
  case else : print hex(i) "   " hex(o) "    " e  '"   " hex(crc32(strptr s, len s))
end select

Title: Re: Help needed with checksums
Post by: Charles Pegge on February 03, 2019, 12:48:25 PM

I am adding the checksum code to o2

This is now converted to asm:

Code: [Select]

  '
  endif
  '
  '
  'CALCULATE AND SET CHECKSUM
  '==========================
  '
  int *ck 'checksum
  sys ps=strptr(dll)
  dword b at ps+60 'PE header offset
  @ck=ps+b+0x58 'checksum location
  ck=0 'clear checksum
  '
  uint ls  'byte length of data
  ls=len(dll)
                   'word *pd 'input
  xor eax,eax      'uint ca 'checksum accumulator
  xor edx,edx      'uint uw 'upper word      '
  mov rsi,ps       '@pd=ps
  mov ecx,ls       'int j 'iterator      
  (                'for j=1 to ls step 2 'each word
    mov dx,[rsi]   '
    add eax,edx    '  ca+=pd
    mov edx,eax    '  uw=ca>>16
    shr edx,16     '
    and eax,0xffff '  ca and=0xffff
    add eax,edx    '  ca+=uw
    add rsi,2      '  @pd+=2
    sub ecx,2      '
    jg repeat      '
  )                'next
  'final           '
  mov edx,eax      'uw=ca>>16
  shr edx,16       '
  add eax,edx      'ca=uw+ca
  and eax,0xffff   'ca and= 0xffff
  add eax,ls       'ca+=ls 'add in byte length of data
  addr rsi,ck      'ck=ca 'set checksum
  mov [rsi],eax    '
  '

Title: Re: Help needed with checksums
Post by: Arnold on February 04, 2019, 02:40:26 AM

Hi Charles,

I am still overwhelmed by the amount of information that is behind the links you mentioned. And at sunshine2k I also found a nice PE viewer which will help me to learn more about the PE file format.

Roland

Title: Re: Help needed with checksums
Post by: Mike Lobanovsky on February 04, 2019, 07:25:33 AM

Quote

http://bytepointer.com/resources/microsoft_pe_checksum_algo_distilled.htm

Charles,

That info was quite new to me. Thanks for the link!

Title: Re: Help needed with checksums
Post by: Charles Pegge on February 04, 2019, 08:35:38 AM

Thanks, Mike and Roland for exploring the subject :)

I've updated OxygenBasicProgress.zip including the Checksum. I hope this will improve our VirusTotal score.

This version uses self-compiled o2, but the final FB version is still included as inc\OXSC\oxygen0.dll.

Title: Re: Help needed with checksums
Post by: JRS on February 04, 2019, 08:47:06 AM

Charles,

Is O2-Classic going to remain a FB centric branch or is the goal to merge O2-DEV into that branch?

Title: Re: Help needed with checksums
Post by: Charles Pegge on February 04, 2019, 09:50:06 AM

Hi John,

Maintaining an extra branch is unsustainable, but we can keep the FB version as an ancestor.

The new o2 pads UDTs correctly, in compliance with C, and treats numeric equates as 32bit values by default, which required some adjustments to the include files.

Title: Re: Help needed with checksums
Post by: JRS on February 04, 2019, 11:01:15 AM

I thought you were going to release a set of examples that were tested with self compile. It seems your direction is to use existing examples and slowly merge in self compile into the O2-Classic branch. I just need to know what your goals are so I can maintain the samdbox.

Actually the sandbox has little interest by anyone and maybe your Github repo is good enough?

I was unable to update the O2-Classic repo in the sandbox with the latest build. I get the following error which I don't understand.

Code: [Select]

fatal: unable to stat 'examples/OOP/Containers/.goutputstream-CHIKWZ': No such file or directory

I'm losing interest in the sandbox for O2 myself as well. My goal for 2019 is to stop wasting my time on efforts no one cares about. Sadly this is related to anything to do with BASIC. I'm jumping on board with everyone else that doesn't give a shit.

Title: Re: Help needed with checksums
Post by: Aurel on February 04, 2019, 02:08:42 PM

Quote

which required some adjustments to the include files.

Charles
What kind of adjustment?
I don't like constant changes..i like stability ::)
sorry if this sounds bitter or ...

One of the reasons why I use older versions :D

Title: Re: Help needed with checksums
Post by: Charles Pegge on February 06, 2019, 02:32:57 AM

Hi John,

I think GitLab is more suited to specialised projects being developed in a corporate environment. For instance 3d-printing.

But I hope we can keep BASIC relevant and advantageous - not just an inferior counterpart of C++

Title: Re: Help needed with checksums
Post by: Charles Pegge on February 06, 2019, 02:59:54 AM

Hi Aurel,

It mostly affects 64bit coding.

UDTs are padded out to the size of their largest primitive member.

For instance, in 32bit-mode this structure is 12 bytes long and requires no padding. But in 64bit-mode the members are 8+8+4 bytes rounded up to 8+8+8 = 24 bytes.

Code: [Select]

typedef struct tagNMHDR {
  HWND     hwndFrom; '8
  UINT_PTR idFrom; '8
  UINT     code; '4
'4 bytes padding
} NMHDR;

Also, Numbers and integer-equates are treated as 32bit values (by default) in unprototyped calls.

This is necessary to prevent sign extension into 64bits: 0x80000000 becoming 0xFFFFFFFF80000000.

Title: Re: Help needed with checksums
Post by: JRS on February 06, 2019, 09:23:07 AM

Saving BASIC is about as difficult as saving the planet from global warming. No one cares.

I'll keep the O2-DEV branch going in the sandbox as it has value determining what you fixed since the last update. It seems Roland has taken interest in testing the distribution's examples under self compile. If he wanted to maintain an examples project in the sandbox I would be happy to set him up to accomplish that.

Title: Re: Help needed with checksums
Post by: Arnold on February 07, 2019, 12:18:52 AM

Hi John,

I would like to contribute in some way with the tutorial examples of IUP (now in the version 3.26). IUP is a powerful gui framework, and I think that IUP works well with OxygenBasic in 32-bit and 64-bit. The examples are well documented in the help file of IUP and the code can be compared with the LUA and C language. Due to the size of the required files (the DLLs should also be provided) this would most probably exceed the intent of Oxygenbasic.

But I can not do that as a maintainer, this goes way beyond my capabilities and interests. I have to finish the last major example in Chapter 3 of the tutorial and will then upload my work in the current state before I continue with Chapter 4. So you can decide if the project should stay in the sandbox.

Roland

Title: Re: Help needed with checksums
Post by: JRS on February 07, 2019, 09:13:16 AM

Hi Arnold,

Just attach the IUP examples to a post and I'll create a project in the sandbox for it. Thanks for your contributions to the O2 project.

Are you doing anything with LED? I have no plans to create a local repo for the IUP sandbox project and use the sandbox web UI exclusively. I would be happy to set you up so you can do the same.

Oxygen Basic

Programming => Problems & Solutions => Topic started by: Arnold on January 30, 2019, 05:07:26 AM