CRC64

Раздел посвящен программированию с использованием Power Basic.
pronto
Постоялец
Постоялец
 
Сообщения: 597
Зарегистрирован: 04.12.2005 (Вс) 6:20
Откуда: Владивосток

CRC64

Сообщение pronto » 25.01.2015 (Вс) 19:26

Здравы будьте, форумчане!

На просторах интернета набрёл на Параллельное вычисление CRC64
Из приложенных к статье исходников на Delphi пытаюсь частично перевести на PowerBasic
Интересует процедура ShaNormalRefreshCRC64, как самая быстрая из представленных...
Код: Выделить всё
procedure ShaNormalRefreshCRC64(var CRC: int64; BufPtr: pointer; BufLen: integer);
asm
  test edx, edx
  jz   @ret
  neg  ecx
  jz   @ret

  push ebx
  push esi
  push eax

  mov ebx, [eax+4]
  mov esi, [eax]
  bswap ebx
  bswap esi
  xor eax, eax

@head:
  test dl, 3
  jz @bodyinit

  mov al, byte [edx]
  inc edx
  xor al, bl
  shrd ebx, esi, 8
  xor ebx, [eax*8 + ByteSwappedTable64]
  shr esi, 8
  xor esi, [eax*8 + ByteSwappedTable64 + 4]
  add ecx, 1
  jnz  @head

  bswap ebx
  bswap esi
  pop eax
  mov [eax+4], ebx
  mov [eax], esi
  pop esi
  pop ebx

@ret:
  ret

@bodyinit:
  sub  edx, ecx
  add  ecx, 8
  jg   @bodydone

  push edi
  push ebp
  mov ebp, ecx
  //  crc64: ebx-lo esi-hi
  //   data: eax-lo ecx-hi
  // buffer: edx-base ebp-count
  //  table: edi-index
@bodyloop:
  mov eax, [edx + ebp - 8]
  xor eax, ebx
  movzx edi, al
  mov ecx, [edx + ebp - 4]
  xor ecx, esi
  mov ebx, [edi*8 + ByteSwappedTable64 + 2048*7]
  mov esi, [edi*8 + ByteSwappedTable64 + 2048*7 + 4]
  movzx edi, ah
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*6]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*6 + 4]
  shr eax, 16
  movzx edi, al
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*5]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*5 + 4]
  movzx edi, ah
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*4]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*4 + 4]

  movzx edi, cl
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*3]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*3 + 4]
  movzx edi, ch
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*2]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*2 + 4]
  shr ecx, 16
  movzx edi, cl
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*1]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*1 + 4]
  movzx edi, ch
  xor ebx, [edi*8 + ByteSwappedTable64 + 2048*0]
  xor esi, [edi*8 + ByteSwappedTable64 + 2048*0 + 4]

  add ebp, 8
  jle @bodyloop

  mov ecx, ebp
  pop ebp
  pop edi

@bodydone:
  sub ecx, 8
  je @result

  xor eax, eax
@tail:
  mov al, byte [edx + ecx]
  xor al, bl
  shrd ebx, esi, 8
  xor ebx, [eax*8 + ByteSwappedTable64]
  shr esi, 8
  xor esi, [eax*8 + ByteSwappedTable64 + 4]
  add ecx, 1
  jnz @tail

@result:
  bswap ebx
  bswap esi
  pop eax;
  mov [eax+4], ebx
  mov [eax], esi
  pop esi
  pop ebx
  end;

Объявление примет вид Function ShaNormalRefreshCRC64(ByVal BufPtr As Byte Ptr, BufLen As Dword) As Quad.
А вот с телом функции, даже и не знаю, нужно что-то делать или нет?..

Ещё есть инициализация таблиц:
Код: Выделить всё
function CRC64Init: boolean;
const
  EcmaPoly= $42F0E1EBA9EA3693; //ECMA DLT standard (normal form), reflected form = $C96C5795D7870F42;
  //Other found polinomials
  OldProteinReflectedPoly= $d800000000000000; //Bad poly (reflected ISO 3309) - too many collisions on proteins with two mutations
  NewProteinReflectedPoly= $95AC9329AC4BC9B5; //By David T. Jones for protein data banks(reflected form)
var
  Poly, ReflectedPoly, c: int64;
  i, j: integer;
begin;
  Poly:=EcmaPoly;

  ReflectedPoly:=$C96C5795D7870F42;
  //ReflectedPoly:=NewProteinReflectedPoly;

  for i:=0 to 255 do begin;
    c:=i;
    for j:=1 to 8 do if odd(c)
                     then c:=(c shr 1) xor ReflectedPoly
                     else c:=(c shr 1);
    ReflectedTable64[0][i]:=c;

    c:=i;
    c:=c shl 56;
    for j:=1 to 8 do if c<0
                     then c:=(c shl 1) xor Poly
                     else c:=(c shl 1);
    ReferenceTable64[i]:=c;
    ByteSwap(c);
    ByteSwappedTable64[0][i]:=c;
    end;

  for i:=0 to 255 do begin;
    c:=ReflectedTable64[0][i];
    for j:=1 to 7 do begin;
      c:=(c shr 8) xor ReflectedTable64[0][byte(c)];
      ReflectedTable64[j][i]:=c;
      end;
    c:=ByteSwappedTable64[0][i];
    for j:=1 to 7 do begin;
      c:=(c shr 8) xor ByteSwappedTable64[0][byte(c)];
      ByteSwappedTable64[j][i]:=c;
      end;
    end;

  Result:=true;

' необходимость дальнейших строк сомнительна
  c:=-1; ReferenceRefreshCRC64(c,@ReferenceTable64[0],SizeOf(ReferenceTable64));
  Result:=Result and ($305CD291B39AA09A=not c);

  c:=-1; NormalRefreshCRC64(c,@ByteSwappedTable64[0,0],SizeOf(ByteSwappedTable64));
  Result:=Result and ($F0347B5C2C7411D2=not c);
  c:=-1; ShaNormalRefreshCRC64(c,@ByteSwappedTable64[0,0],SizeOf(ByteSwappedTable64));
  Result:=Result and ($F0347B5C2C7411D2=not c);

  if ReflectedPoly=$C96C5795D7870F42 then begin;
    c:=-1; ReflectedRefreshCRC64(c,@ReflectedTable64[0,0],SizeOf(ReflectedTable64));
    Result:=Result and ($014ED9B63590C55E=not c);
    c:=-1; ShaReflectedRefreshCRC64(c,@ReflectedTable64[0,0],SizeOf(ReflectedTable64));
    Result:=Result and ($014ED9B63590C55E=not c);
    end;

  end;

И вспомогательная функция:
Код: Выделить всё
procedure ByteSwap(var Value: int64);
asm
  mov ecx, [eax]
  mov edx, [eax+4]
  bswap ecx
  bswap edx
  mov [eax+4], ecx
  mov [eax], edx
  end;

Примет вид:
Код: Выделить всё
Function SwapQuad(ByVal QuadVar As Quad) As Quad
Prefix "ASM"
  mov ecx, [eax]
  mov edx, [eax+4]
  bswap ecx
  bswap edx
  mov [eax+4], ecx
  mov [eax], edx
End Prefix
End Function


Всё, что касается заполнения таблиц перевёл так:
Код: Выделить всё
%EcmaPoly = &H42F0E1EBA9EA3693&&
%ReflectedPoly = &HC96C5795D7870F42&&

Global ByteSwappedTable64() As Quad ' array[0..7] of array[0..255] of int64
Global ReflectedTable64() As Quad   

Sub InitCRC_64
   Local v As Quad
   Register I As Dword, J As Dword

   ReDim ByteSwappedTable64(7, 255)
   ReDim ReflectedTable64(7, 255)

   For I = 0 To 255
      v = I

      For J = 1 To 8
         If v And 1 Then
            Shift Right V, 1
            v = v Xor %ReflectedPoly
         Else
            Shift Right v, 1
         End If
      Next J

      ReflectedTable64(0, I) = v

      v = I
      Shift Left v, 56

      For J = 1 To 8
         If v < 0 Then
            Shift Left v, 1
            v = v Xor %EcmaPoly
         Else
            Shift Left v, 1
         End If
      Next J

      ByteSwappedTable64(0, I) = SwapQuad(ByVal v)
   Next I

   For I = 0 To 255
      v = ReflectedTable64(0, I)

      For J = 1 To 7
         Shift Right v, 8
         ReflectedTable64(J, I) = v Xor ReflectedTable64(0, CByt(v))
      Next J

      v = ByteSwappedTable64(0, I)

      For J = 1 To 7
         Shift Right v, 8
         ByteSwappedTable64(J, I) = v Xor ByteSwappedTable64(0, CByt(v))
      Next J
   Next I
End Sub

После испраления всех ошибок встанет вопрос проверки выдаваемых CRC64 этим алгоритмом с CRC64 некой проверенной софтины...
O, sancta simplicitas!

ZozBale
Новичок
Новичок
Аватара пользователя
 
Сообщения: 46
Зарегистрирован: 17.02.2012 (Пт) 8:37

Re: CRC64

Сообщение ZozBale » 14.03.2015 (Сб) 20:03

Если нужен любой 64-битный хэш, то рекомендую FNV64. Исходный код тривиален, а перемешивание бит получается очень хорошее. https://ru.wikipedia.org/wiki/FNV
http://programmers.stackexchange.com/qu ... -and-speed


Вернуться в Power Basic

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12

    TopList