CRC

New to FreeBASIC? Post your questions here.
Fragmeister
Posts: 545
Joined: Nov 08, 2005 14:36

CRC

Postby Fragmeister » Mar 17, 2006 3:40

I've been learning about CRC's lately, and came up with the following code:

Code: Select all

declare function hash(msg as ubyte ptr,ml as ulongint,poly as ubyte) as ubyte
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
input "Message to hash: ",msg$
print hash(@msg$,len(msg$),7)
sleep
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
function hash(msg as ubyte ptr,ml as ulongint,poly as ubyte) as ubyte
        dim msgbits as ulongint,msgbyte as ulongint,cbit as ulongint
        dim register as ubyte,out_bit as ubyte,in_bit as ubyte
        'set msgbits to len of msg in bits.
        msgbits=ml*8
        'set msgbyte+cbit to 1
        msgbyte=1
        cbit=7
        '& set register to &b00000000.
        register=0
        'now we begin.
        for i=1 to msgbits
                'print "Register:     ";bin$(register)
                'get status of bit about to be popped out of register.
                out_bit=bit(register,7)
                'shift bits in register 1 place to left (eliminating the bit we just checked)
                register=register shl 1
                'print "Shifted:      ";bin$(register)
                'get a new bit from the msg and put it into the other end of the register.
                in_bit=bit(msg[msgbyte],cbit)
                if in_bit=0 then register=bitreset(register,0) else register=bitset(register,0)
                'print "Added:        ";bin$(register)
                'if the "popped" bit is 1, then xor the register with the poly.
                if out_bit<>0 then register=register xor poly
                '"increment" the bit, and if this is bit 0 of the current msg
                'byte, then increment that,too.
                if cbit>0 then cbit-=1 else cbit=7:msgbyte+=1
                'repeat.
        next i
        'the register now contains the remainder of the msg divided by the poly.
        return register
end function


It seems to work for me, but I'm a total n00b at this, and don't quite understand the math behind it. (but I'm almost there.) What I want to know, does this code actually generate a valid CRC code? (assuming of course that a 1 byte code would actually be useful!)
yetifoot
Posts: 1710
Joined: Sep 11, 2005 7:08
Location: England
Contact:

Postby yetifoot » Mar 20, 2006 17:05

i havent got time to look at it but heres my idea for how you should test it.

generate as many possible combinations of intended data possible, and use the function to generate the checksums, storing them as you go.

If two different input values give the same checksum this is a collision, and is what you want to avoid.

If you get lots of collisions then its not a very good checksum function for the data.

However if you throw enough data (even at a really good checksummer) you will always get some collisions, but you want them to be as minimal as possible.
D.J.Peters
Posts: 7191
Joined: May 28, 2005 3:28

Postby D.J.Peters » Mar 20, 2006 20:21

If you test the hash code same hash values has to many difrent sources.

But for an beginner realy nice work.

Joshy

Code: Select all

option explicit
function hash(msg as ubyte ptr,ml as ulongint,poly as ubyte) as ubyte
        dim msgbits as ulongint,msgbyte as ulongint,cbit as ulongint
        dim register as ubyte,out_bit as ubyte,in_bit as ubyte
        dim as integer i
        'set msgbits to len of msg in bits.
        msgbits=ml*8
        'set msgbyte+cbit to 1
        msgbyte=1
        cbit=7
        '& set register to &b00000000.
        register=0
        'now we begin.
        for i=1 to msgbits
                'print "Register:     ";bin$(register)
                'get status of bit about to be popped out of register.
                out_bit=bit(register,7)
                'shift bits in register 1 place to left (eliminating the bit we just checked)
                register=register shl 1
                'print "Shifted:      ";bin$(register)
                'get a new bit from the msg and put it into the other end of the register.
                in_bit=bit(msg[msgbyte],cbit)
                if in_bit=0 then register=bitreset(register,0) else register=bitset(register,0)
                'print "Added:        ";bin$(register)
                'if the "popped" bit is 1, then xor the register with the poly.
                if out_bit<>0 then register=register xor poly
                '"increment" the bit, and if this is bit 0 of the current msg
                'byte, then increment that,too.
                if cbit>0 then cbit-=1 else cbit=7:msgbyte+=1
                'repeat.
        next i
        'the register now contains the remainder of the msg divided by the poly.
        return register
end function


'
' main
'
dim as integer hits(255)
dim as integer msg
for msg=0 TO 255*4 ' try 6,7,8 and see the relation betwen
                   ' the number of hits and the input stream
  hits(hash(@msg,4,7))+=1
next
for msg=0 to 255
  if hits(msg)>1 then ? "hashvalue = "; msg, "has more than one hits=" ;hits(msg)
next
sleep
end
Last edited by D.J.Peters on Jul 30, 2010 16:44, edited 3 times in total.
Antoni
Posts: 1393
Joined: May 27, 2005 15:40
Location: Barcelona, Spain

Postby Antoni » Mar 20, 2006 20:26

Get FileAlyzer:
http://www.safer-networking.org/en/filealyzer/
It's a freeware file analyzer tool, with multiple uses: Win resource viewer, hex viewer, text strings viewer, Import-export table viewer, md5 and....CRC.
You can test your program with any file in your system, then check the results with FileAlyzer
Fragmeister
Posts: 545
Joined: Nov 08, 2005 14:36

Postby Fragmeister » Mar 20, 2006 23:10

@D.J.Peters: I realized after I posted this that when I use "@msg$", it returns a pointer to the string descriptor. I modified the code to NOT do that, and it worked a lot better. I just couldn't get on the internet to post it. And thanks for the support!

Here's the new version, that can do a 64 bit hash as well, and a wrapper function to do the hash of a file.

Code: Select all

declare function hash_8(msg as ubyte ptr,ml as ulongint,poly as ubyte) as ubyte
declare function hash_64(msg as ulongint ptr,ml as ulongint,poly as ulongint) as ulongint
declare function hash_64_file(file as string) as ulongint
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
dim msg as zstring*1024
input "Message to hash: ",mesg$
msg=mesg$
?hex$(hash_64_file("hash.bas"))
sleep
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
function hash_8(msg as ubyte ptr,ml as ulongint,poly as ubyte) as ubyte
        dim msgbits as ulongint,msgbyte as ulongint,cbit as ulongint
        dim register as ubyte,out_bit as ubyte,in_bit as ubyte
        'set msgbits to len of msg in bits.
        msgbits=ml*8
        'set msgbyte+cbit to 1
        msgbyte=0
        cbit=7
        '& set register to &b00000000.
        register=0
        'now we begin.
        for i=1 to msgbits
                'print "Register:     ";bin$(register)
                'get status of bit about to be popped out of register.
                out_bit=bit(register,7)
                'shift bits in register 1 place to left (eliminating the bit we just checked)
                register=register shl 1
                'print "Shifted:      ";bin$(register)
                'get a new bit from the msg and put it into the other end of the register.
                in_bit=bit(msg[msgbyte],cbit)
                if in_bit=0 then register=bitreset(register,0) else register=bitset(register,0)
                'print "Added:        ";bin$(register)
                'if the "popped" bit is 1, then xor the register with the poly.
                if out_bit<>0 then register=register xor poly
                '"increment" the bit, and if this is bit 0 of the current msg
                'byte, then increment that,too.
                if cbit>0 then cbit-=1 else cbit=7:msgbyte+=1
                'repeat.
        next i
        'the register now contains the remainder of the msg divided by the poly.
        return register
end function

function hash_64(msg as ulongint ptr,ml as ulongint,poly as ulongint) as ulongint
        dim msgbits as ulongint,msgli as ulongint,cbit as ulongint
        dim register as ulongint,out_bit as ubyte,in_bit as ubyte
        'set msgbits to len of msg in bits.
        msgbits=ml*8
        'set msgbyte+cbit to 1
        msgli=0
        cbit=7
        '& set register to &b00000000.
        register=0
        'now we begin.
        for i=1 to msgbits
                'print "Register:     ";bin$(register)
                'get status of bit about to be popped out of register.
                out_bit=bit(register,63)
                'shift bits in register 1 place to left (eliminating the bit we just checked)
                register=register shl 1
                'print "Shifted:      ";bin$(register)
                'get a new bit from the msg and put it into the other end of the register.
                in_bit=bit(msg[msgli],cbit)
                if in_bit=0 then register=bitreset(register,0) else register=bitset(register,0)
                'print "Added:        ";bin$(register)
                'if the "popped" bit is 1, then xor the register with the poly.
                if out_bit<>0 then register=register xor poly
                '"increment" the bit, and if this is bit 0 of the current msg
                'byte, then increment that,too.
                if cbit>0 then cbit-=1 else cbit=63:msgli+=1
                'repeat.
        next i
        'the register now contains the remainder of the msg divided by the poly.
        return register
end function

function hash_64_file(file as string) as ulongint
        dim f,fp as ubyte ptr
        f=freefile
        open file for binary as #f
        fp=callocate(lof(f))
        while not eof(f)
                get #f,,fp[loc(f)-1]
        wend
        'close f
        dim res as ulongint
        res=hash_64(fp,lof(f)/8,&b0111011101110111011101110111011101110111011101110111011101110111)
        close f
        deallocate fp
        return res
end function
D.J.Peters
Posts: 7191
Joined: May 28, 2005 3:28

Postby D.J.Peters » Mar 21, 2006 4:00

You don't need to read byte by byte in binary mode.
http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgGetfileio

get #hFile,,YourBytePointer,lof(hFile)

Joshy
Fragmeister
Posts: 545
Joined: Nov 08, 2005 14:36

Postby Fragmeister » Mar 21, 2006 17:26

D.J.Peters wrote:You don't need to read byte by byte in binary mode.
http://www.freebasic.net/wiki/wikka.php?wakka=KeyPgGetfileio

get #hFile,,YourBytePointer,lof(hFile)

Joshy

/me=n00b.
I should have known that one... or figured it out somehow...
Thanks, though! That'll really speed it up.
Actually, though, I wrote a test program for hash_64(the new version), and ran 10000 iterations using a string length of anywhere from 256-1024 chars. It completed in about 16.5 seconds, with a 99.something percent success rate!
counting_pine
Site Admin
Posts: 5826
Joined: Jul 05, 2005 17:32
Location: Manchester, Lancs

Postby counting_pine » Mar 21, 2006 19:42

You mean your program has an error rate of at least 1 in 10000? Sounds like something's going wrong.
Maybe I'm just being a perfectionist, but I prefer programs to have an error rate of 0 in 10000.
DrV
Site Admin
Posts: 2116
Joined: May 27, 2005 18:39
Location: Midwestern USA
Contact:

Postby DrV » Mar 21, 2006 20:52

That just means that there were some collisions; CRC always has some collisions unless your data's size is smaller than the size of the CRC. :)
Fragmeister
Posts: 545
Joined: Nov 08, 2005 14:36

Postby Fragmeister » Mar 22, 2006 3:12

DrV wrote:That just means that there were some collisions; CRC always has some collisions unless your data's size is smaller than the size of the CRC. :)

it would be mathematically impossible to have no collisions. And wouldn't that be if the data's size was smaller than or equal to the size of the crc?

And by using filealyzer, I found out that my program does not generate a valid crc. But besides that, it seems to work pretty good!

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 1 guest