unit pseudohadamard;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, Gmp, Math;

procedure pseudoHadamardTransformation(var daten: array of mpz_t; modul: mpz_t; invers: boolean); overload;
procedure pseudoHadamardTransformation(var daten: array of mpz_t; Ordnung, Verschiebung: longint; modul: mpz_t; var buff: mpz_t; invers: boolean); overload;

implementation

procedure pseudoHadamardTransformation(var daten: array of mpz_t; modul: mpz_t; invers: boolean);
var
  buff: mpz_t;
begin
  if length(daten)<>round(power(2,round(ln(length(daten))/ln(2)))) then
    raise Exception.create('Die Länge der Daten für eine Pseudohadamardtransformation muss eine Zweierpotenz sein (und nicht '+inttostr(length(daten))+')!');
  mpz_init(buff);
  pseudoHadamardTransformation(daten,length(daten),0,modul,buff,invers);
  mpz_clear(buff);
end;

procedure pseudoHadamardTransformation(var daten: array of mpz_t; Ordnung, Verschiebung: longint; modul: mpz_t; var buff: mpz_t; invers: boolean);
var
  i: longint;
begin
  Ordnung:=Ordnung div 2;
  if Ordnung>1 then
    for i:=0 to 1 do
      pseudoHadamardTransformation(daten,Ordnung,Verschiebung + i*Ordnung,modul,buff,invers);

  if invers then begin
    for i:=0 to Ordnung-1 do begin
      mpz_set(buff,daten[Verschiebung+i]);
      mpz_sub(daten[Verschiebung+i],daten[Verschiebung+i],daten[Verschiebung+i+Ordnung]);         // a = a' - b
      mpz_mod(daten[Verschiebung+i],daten[Verschiebung+i],modul);

      mpz_mul_ui(daten[Verschiebung+i+Ordnung],daten[Verschiebung+i+Ordnung],2);                  // b = 2*b'
      mpz_sub(daten[Verschiebung+i+Ordnung],daten[Verschiebung+i+Ordnung],buff);                  // - a'
      mpz_mod(daten[Verschiebung+i+Ordnung],daten[Verschiebung+i+Ordnung],modul);
    end;
  end
  else
    for i:=0 to Ordnung-1 do begin
      mpz_set(buff,daten[Verschiebung+i]);
      mpz_mul_ui(daten[Verschiebung+i],daten[Verschiebung+i],2);                                  // a' = 2 * a
      mpz_add(daten[Verschiebung+i],daten[Verschiebung+i],daten[Verschiebung+i+Ordnung]);         // + b
      mpz_mod(daten[Verschiebung+i],daten[Verschiebung+i],modul);

      mpz_add(daten[Verschiebung+i+Ordnung],daten[Verschiebung+i+Ordnung],buff);                  // b' = a + b
      mpz_mod(daten[Verschiebung+i+Ordnung],daten[Verschiebung+i+Ordnung],modul);
    end;
end;

end.