Where can I find a CRC32 68000 code?

[Maartau]

Hiya dudes,

I'm asking if there any already existing CRC32 source code in 68000.

(I haven't take enough time ATM to consider the question ).

See you,

[Mug UK]

I'm sure there's one for the ST out there somewhere but a quick Google found one in an Amiga FTP site?

http://ftp.urz.uni-heidelberg.de/ftp/pub/amiga/dev/asm/

Filename: CRC32.LHA

You might need to convert it to ST format text as Amiga text doesn't feature proper linefeeds.

[daeghnao]

You might need to convert it to ST format text as Amiga text doesn't feature proper linefeeds.

It's full of linefeeds! What it lacks is carriage returns This is the same format as is used on most kinds of Unix, by the way.

Attached is the relevant source code with TOS-compatible line terminators.

[Mug UK]

Ach .. linefeeds / carriage returns

Oh well ..

[Maartau]

Many thanks for your so fast reply .

I have to re-read the main algo which can be used ...

[dsp56001]

Hello,

There is a CRC32 code i used to use many years ago and it seems to be optimised for the m68k.
This piece of art was written by the TOSCREW aka makers of the ARJ packer for ATARI ST.

Good night all.

[Maartau]

ARJ packer for ATARI ST.

Yes there's many things to do with that packer, I haven't found the moment to go in ATM .

[Nyh]

I'm asking if there any already existing CRC32 source code in 68000.

There is a lot to tell about CRC coding on the 68000. There is small code, fast code and everything in between. Here some simple code. It first generates a CRC table on the stack and then calculates the CRC32 of the memory block.

Code: Select all

;
; ARJ CRC function
; Size optimized
; Copyleft 1993 Mr Ni! (the Great) of the TOS-crew
;
; ulong crc_buf(char *str, ulong len)
;
; CALL:
; D0 = #bytes (long)
; A0 = buffer
;
; Return:
; D0 = CRC-code
;
; uses 1kB buffer on stack
;
crc_buf:
     move.l  d3,-(sp)
     move.l  d0,-(sp)
     lea     (sp),a1
     lea     -1024(sp),sp
     moveq   #0,d0
     subq.b  #1,d0
     move.l  #$EDB88320,d2
.loop_0:
     moveq   #7,d3
     move.l  d0,d1
.loop_1:
     lsr.l   #1,d1
     bcc.s   .next
     eor.l   d2,d1
.next:
     dbra    d3,.loop_1
     move.l  d1,-(a1)
     dbra    d0,.loop_0
     move.l  1024(sp),d0
     moveq   #-1,d1
.crc_loop:
     moveq   #0,d2
     move.b  (a0)+,d2
     eor.b   d1,d2
     lsr.l   #8,d1
     lsl.w   #2,d2
     move.l  0(a1,d2.w),d2
     eor.l   d2,d1
     subq.l  #1,d0
     bne.s   .crc_loop
     lea     1028(sp),sp
     not.l   d1
     move.l  d1,d0
     move.l  (sp)+,d3
     rts

;d0,d1,d2,d3,d4,d5,d6,d7,a0,a1,a2,a3,a4,a5,a6,a7,sp
*******************************************************************************

     END

Hans Wessels

[Nyh]

http://ftp.urz.uni-heidelberg.de/ftp/pub/amiga/dev/asm/

Filename: CRC32.LHA

You might need to convert it to ST format text as Amiga text doesn't feature proper linefeeds.

Better yet, throw it immediately in the trash can. What an ugly piece of code! I suspect it was generated by a 32 bit C compiler. It uses 32 bit operators even though it only needs the LSB. Wasting a lot of CPU cycles in the middle of a CRC32 loop. :-S

Hans Wessels

[Mug UK]

Ah right .. was the only one I found after a quick Google.

[Maartau]

Many thanks for your source Mister NYH .


And happy new year 2008 to everyone again !

[Maartau]

My next question is about CRC 16:

Code: Select all

crc16= X^16 + X^15 + X^2 + 1 

How can I convert this to 68000?

Yep, I'm also looking for 16 bits CRC algo, if you can help .


See you,

[Nyh]

My next question is about CRC 16:

Code: Select all

crc16= X^16 + X^15 + X^2 + 1 

How can I convert this to 68000?

This is thae standard CRC poly. The representation is: 0xA001.

Problem is I have only very high speed CRC16 code in ARJBETA and no small CRC16 code. In C it is quite simple:

Code: Select all

/************************************************************************
 ****************              LHA CRC              *********************
 ************************************************************************/

/*
 * uint16 crc16(const uint8 *str, long len, uint16 crc, const uint16 *crc_table)
 *
 * Calculate the CRC of a buffer.
 *
 * Parameters:
 *
 * str				- pointer to buffer.
 * len				- length of buffer.
 * crc				- crc start value.
 * crc_table	- pointer to crc table.
 *
 * Result: CRC of buffer.
 */

#define NLIT 256

uint16 crc16(const uint8 * str, long len, uint16 crc,
             const uint16 * crc_table)
{
  do
  {
    uint8 kar = *str++;

    kar ^= (uint8) crc;
    crc >>= 8;
    crc ^= crc_table[kar];
  }
  while (--len != 0);

  return crc;
}

uint16 lha_init_crc(void)
{
  return 0;
}

void free_crc16_table(uint16 * table)
{
  if (table != NULL)
  {
    free(table);
  }
}

/*
 * uint16 *make_crc16_table(uint16 crc_poly)
 *
 * Initialize the CRC table used by the buf_crc() function.
 *
 * Result: NULL if out of memory, pointer to crc table otherwise.
 */

uint16 *make_crc16_table(uint16 crc_poly)
{
  uint16 *crc_table;

  if ((crc_table = malloc(NLIT * sizeof(uint16))) != NULL)
  {
    uint16 kar;

    kar = NLIT - 1;

    do
    {
      int i = 7;
      uint16 crc = kar;

      do
      {
        if (crc & 1)
        {
          crc >>= 1;
          crc ^= crc_poly;
        }
        else
        {
          crc >>= 1;
        }
      }
      while (i-- != 0);

      crc_table[kar] = crc;
    }
    while (kar-- != 0);
  }

  return crc_table;
}

In assembly you would do something like this (warning: not tested):

Code: Select all

crc16_buf:
     move.l  d3,-(sp)
     move.w  d0,-(sp)
     lea     (sp),a1
     lea     -512(sp),sp
     moveq   #0,d0
     subq.b  #1,d0
     move.w  #$A001,d2
.loop_0:
     moveq   #7,d3
     move.w  d0,d1
.loop_1:
     lsr.w   #1,d1
     bcc.s   .next
     eor.w   d2,d1
.next:
     dbra    d3,.loop_1
     move.w  d1,-(a1)
     dbra    d0,.loop_0
     move.w  512(sp),d0
     moveq   #-1,d1
.crc_loop:
     moveq   #0,d2
     move.b  (a0)+,d2
     eor.b   d1,d2
     lsr.w   #8,d1
     add.w   d2,d2
     move.w  0(a1,d2.w),d2
     eor.w   d2,d1
     subq.l  #1,d0
     bne.s   .crc_loop
     lea     514(sp),sp
     not.w   d1
     move.w  d1,d0
     move.l  (sp)+,d3
     rts

Note: this is the crc32 code converted to 16 bits.

Note 2: if you calculate the CRC multiple times it is smart to store the CRC table and not to recalculate the table every function call.

Hans Wessels

[Maartau]

"I'll do my own tests using your code"...

...Thanks Hans .

[Nyh]

"I'll do my own tests using your code"...

I almost forgot:

Code: Select all

     moveq   #-1,d1

Is the initialisator of the CRC sum. In most applications it is either -1 ($FFFF) or 0. In the ARJ CRC -1 is used but in LHA 0 is used. I don't know why you need both 16 and 32 bit CRC routines but if it is for compatibiliry reasons you need the correct initialisator.

Hans Wessels

[Maartau]

I don't know why you need both 16 and 32 bit CRC routines.

Hans Wessels

I only needed CRC 32 for checking some datas... The 16 was just for my "curiousity"...


For "curious" ppl ...

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

[Dio]

I've found Fletcher-16 (closely related to Zip's 'CRC') is a pretty good compromise between accuracy and performance and very easily implemented on 68k. I've got some code for that if you'd like?

[Maartau]

I've found Fletcher-16 (closely related to Zip's 'CRC') is a pretty good compromise between accuracy and performance and very easily implemented on 68k. I've got some code for that if you'd like?

All code always welcome .

[Dio]

Righty-ho then.

Code: Select all

		; This implements Fletcher-16 (sum 16-bit words mod 65535)
		; It's not a 'fast' implementation of the algorithm, but the access to the
		; carry flag makes that less important

		; There's two entrypoints, for adding 32 and 16 bits
		; Input is d0, checksum is the two words at (a0)
checksum32:
		move.l d0,d2

		add.w (a0), d0
		bcc cs1
		addq.w #1,d0
cs1:	move.w d0,d1
		add.w 2(a0),d1
		bcc cs2
		addq.w #1,d1
cs2:

		swap d2
		add.w d2,d0
		bcc cs3
		addq.w #1,d0
cs3:	add.w d0,d1
		bcc cs4
		addq.w #1,d1
cs4:	move.w d0,(a0)
		move.w d1,2(a0)
		rts


checksum16:
		add.w (a0), d0
		bcc cs1a
		addq.w #1,d0
cs1a:	move.w d0,d1
		add.w 2(a0),d1
		bcc cs2a
		addq.w #1,d1
cs2a:	move.w d0,(a0)
		move.w d1,2(a0)
		rts

[Maartau]

Righty-ho then.

Many thanks ( ) .

[CTRL C/V done].


DEVPACK rulezz .

[Nyh]

Righty-ho then.

Why this implementation?

I would expect something like:
int32 fletcher(int32 sum, int32 count, int16* data)
; d0 = sum
; d1= number of words to do
; a0 = pointer to word aligned data

Hans Wessels

[Dio]

I was checksumming register values - it's from an emulator CPU tester - so it was generally for words or longs only.

[Maartau]

Digging out that topic ...

Cleaning the recent posts to have a more oriented & precise questions : CRC's are a wide question & I wasn't aware of all "details"

[czietz]

There are many different 32 bit CRC algorithms: http://reveng.sourceforge.net/crc-catal ... at-bits.32 Which one do you need?

[npomarede]

Hi

$EDB88320 is the so called "reversed" crc32, in the sense that it uses the same polynomial $04C11DB7, except you don't shift bits to the left, but to the right (which can be more efficient depending on the cpu little/big endianess)
See for example : https://www.hackersdelight.org/hdcodetxt/crc.c.txt and crc32a against crc32b.

I guess you try to compare your asm result with an existing binary on your PC, in which case you need to know which variant the PC is using. 0x04c11db7 is the IEEE 802.3 recommandation, so maybe that's what you should use to compare with other programs.

Nicolas