Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Firebird, InterBase Новый топик    Ответить
 Особенности Hash()  [new]
SHS_SHS
Member

Откуда:
Сообщений: 130
Доброго времени суток.
Понадобилось повторить на Delphi функцию hash() из FB. Поиск по форуму выдал это 14398246. В интернете нашел такую реализацию для HashELF64:
function HashELF64(const aBuf; aBufSize: Integer): Int64;
type
  TByteArray = array[0..MaxInt - 1] of Byte;
var
  i: Integer;
  x: Int64;
begin
  Result := 0;
  for i := 0 to aBufSize - 1 do
  begin
    Result := (Result shl 4) + TByteArray(aBuf)[i];
    x := Result and $F000000000000000;
    if (x <> 0) then
      Result := Result xor (x shr 56);
    Result := Result and (not x);
  end;
end;

если строка на входе до 20 символов, то все нормально, но после 20 результат hash() FB3.0 и Delphi отличаются.
Так например hash строки "12345678901234567890":
8526506766684599104 - FB
 696865270170176576 - Delphi

Если изменить код так:
function HashELF64(const aBuf; aBufSize: Integer): Int64;
type
  TByteArray = array[0..MaxInt - 1] of Byte;
var
  i: Integer;
  x: Int64;
begin
  Result := 0;
  for i := 0 to aBufSize - 1 do
  begin
    Result := (Result shl 4) + TByteArray(aBuf)[i];
    if Result < 0 then // <========================= дописать это
    begin
      Result := Abs(Result);
      Continue;
    end;
    x := Result and $F000000000000000;
    if (x <> 0) then
      Result := Result xor (x shr 56);
    Result := Result and (not x);
  end;
end;

то для строки "12345678901234567890" hash становится одинаковым. Но это не решает проблему. Для более длинных строк hash разный. Я понимаю, что дело в переполнении Int64, но как подправить не догоняю.
5 ноя 19, 00:06    [22009620]     Ответить | Цитировать Сообщить модератору
 Re: Особенности Hash()  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 50343

SHS_SHS
Я понимаю, что дело в переполнении Int64

Нет, дело в том, что в Дельфи shr это логический сдвиг, а не арифметический. Знак не
расширяется в отличии от Си. А арифметического у неё нет. Используй деление.

Posted via ActualForum NNTP Server 1.5

5 ноя 19, 01:30    [22009643]     Ответить | Цитировать Сообщить модератору
 Re: Особенности Hash()  [new]
SHS_SHS
Member

Откуда:
Сообщений: 130
Спасибо. Сейчас работает.
Может кому пригодится:
function HashELF64(const aBuf; aBufSize: Integer): Int64;
type
  TByteArray = array[0..MaxInt - 1] of Byte;
var
  i: Integer;
  x: Int64;
begin
  Result := 0;
  for i := 0 to aBufSize - 1 do
  begin
    Result := (Result shl 4) + TByteArray(aBuf)[i];
    x := Result and $F000000000000000;
    if (x <> 0) then
      Result := Result xor (x div $100000000000000); // Result := Result xor (x shr 56);
    Result := Result and (not x);
  end;
end;
5 ноя 19, 09:31    [22009731]     Ответить | Цитировать Сообщить модератору
 Re: Особенности Hash()  [new]
sysdba22
Member

Откуда:
Сообщений: 252
Кому надо, функция на TypeScript для Node или браузера:
const hashELF64 = (s: string) => {
  let res = 0n;
  for (const c of [...s]) {
    res = (res << 4n) + BigInt(c.charCodeAt(0));
    const x = res & 0xF000000000000000n;
    if (x !== 0n) {
      res = res ^ (x >> 56n);
    }
    res = res & (~x);
  }
  return res;
};


Работает только с первыми 128 символами ASCII и та же проблема с переполнением, которую на не смог победить. Но, так как у меня строки до 14 символов, от которых вычисляется, то меня устраивает.
10 июн 20, 18:56    [22148970]     Ответить | Цитировать Сообщить модератору
Все форумы / Firebird, InterBase Ответить