SHA-1 Hash in Pure Prolog

:- module(s4c28, [sha1/2]).

:- use_module(library(apply), [foldl/4]).
:- use_module(library(clpfd)).
:- use_module(library(list_util), [take/3, drop/3, replicate/3]).

blocks([], _, []) :- !.
blocks(Bytes, BSize, [Block|NextBlocks]) :-
    take(BSize, 0, Bytes, Block),
    drop(BSize, Bytes, NextBytes),
    blocks(NextBytes, BSize, NextBlocks).

int_bytes_be(I, Bs) :-
    foldl([E, I0, I]>>(
              E in 0..255,
              I #= I0*256 + E),
         Bs, 0, I).

int_bytes_be_64(I, B) :-
    int_bytes_be(I, B),
    length(B, 8), !.

int_bytes_be_32(I, B) :-
    int_bytes_be(I, B),
    length(B, 4), !.

sha1(In, Digest) :-
    In ins 0..255,

    sha1_preprocess(In, Message),

    % process the message in successive 512-bit (64-byte) chunks
    blocks(Message, 64, MsgBlocks),

    % process chunks
    H0 = 0x67452301,
    H1 = 0xefcdab89,
    H2 = 0x98badcfe,
    H3 = 0x10325476,
    H4 = 0xc3d2e1f0,

    foldl([Block, H0-H1-H2-H3-H4, G0-G1-G2-G3-G4]>>(
              sha1_process_chunk(H0-H1-H2-H3-H4, Block, A-B-C-D-E),
              G0 #= (H0 + A) /\ 0xffff_ffff,
              G1 #= (H1 + B) /\ 0xffff_ffff,
              G2 #= (H2 + C) /\ 0xffff_ffff,
              G3 #= (H3 + D) /\ 0xffff_ffff,
              G4 #= (H4 + E) /\ 0xffff_ffff
          ), MsgBlocks, H0-H1-H2-H3-H4, Hh0-Hh1-Hh2-Hh3-Hh4),

    Out #= ((Hh0 << 128) \/ (Hh1 << 96) \/ (Hh2 << 64) \/ (Hh3 << 32) \/ Hh4),
    int_bytes_be(Out, Digest), length(Digest, 20), !.

sha1_preprocess(Input, Message) :-
    length(Input, InL),
    Ml #= InL * 8, % original message length in bits

    % append the bit '1' to the message
    append(Input, [0x80], M1),
    % append zeros to the message st resultant length in bits is
    % congruent to −64 ≡ 448 (mod 512)
    % 64 bits = 8 bytes, 512 bits = 64 bytes
    % -8 ≡ 56 (mod 64)
    K #= (56 - (InL + 1)) mod 64,
    replicate(K, 0, Zeroes),
    append(M1, Zeroes, M2),

    % append the original length as a big-endian 64-bit integer
    int_bytes_be_64(Ml, MlBytes),
    append(M2, MlBytes, Message),

    length(Message, MessageLen),
    0 #= MessageLen mod 64.

leftrotate(I, N, RotI) :-
    WordLen #= 32,
    WordMask #= (1 << WordLen) - 1,
    RotI #= ((I << N) /\ WordMask) \/ (I >> (WordLen - N)).

sha1_process_chunk(H0-H1-H2-H3-H4, Chunk, ChunkHash) :-
    % break each chunk into 16 32-bit (4-byte) big-endian words
    blocks(Chunk, 4, Words_),
    length(Words_, 16),
    maplist(int_bytes_be_32, Words, Words_),

    % extend the 16 32-bit words into 80 32-bit words
    Extra #= 80 - 16,
    length(ExtraWords, Extra),
    append(Words, ExtraWords, ExtendedWords),
    numlist(16, 79, Indices),
    maplist({ExtendedWords}/[I,W]>>(
                I3 is I - 3, I8 is I - 8,
                I14 is I - 14, I16 is I - 16,
                nth0(I3, ExtendedWords, W3),
                nth0(I8, ExtendedWords, W8),
                nth0(I14, ExtendedWords, W14),
                nth0(I16, ExtendedWords, W16),
                W_ is W3 xor W8 xor W14 xor W16,
                leftrotate(W_, 1, W)
            ), Indices, ExtraWords),

    % main loop
    numlist(0, 79, Is),
    foldl({ExtendedWords}/[I, A0-B0-C0-D0-E0, A-B-C-D-E]>>(
              main_loop_step(I, B0-C0-D0, F, K),
              E = D0,
              D = C0,
              leftrotate(B0, 30, C),
              B = A0,
              leftrotate(A0, 5, X),
              nth0(I, ExtendedWords, Wi),
              A #= (X + F + E0 + K + Wi) /\ 0xffff_ffff
          ), Is, H0-H1-H2-H3-H4, ChunkHash).

main_loop_step(I, B-C-D, F, K) :-
    between(0, 19, I),
    F #= (B /\ C) \/ ((\B) /\ D),
    K = 0x5a827999.
main_loop_step(I, B-C-D, F, K) :-
    between(20, 39, I),
    F #= B xor C xor D,
    K = 0x6ed9eba1.
main_loop_step(I, B-C-D, F, K) :-
    between(40, 59, I),
    F #= (B /\ C) \/ (B /\ D) \/ (C /\ D),
    K = 0x8f1bbcdc.
main_loop_step(I, B-C-D, F, K) :-
    between(60, 79, I),
    F #= B xor C xor D,
    K = 0xca62c1d6.

% tests
:- use_module(library(crypto), [hex_bytes/2]).
:- use_module(library(plunit)).

:- begin_tests(s4c28).

test(sha1_empty) :-
    sha1(``, O),
    hex_bytes(Hex, O), !,
    Hex = 'da39a3ee5e6b4b0d3255bfef95601890afd80709'.

test(sha1_dog) :-
    sha1(`The quick brown fox jumps over the lazy dog`, O),
    hex_bytes(Hex, O),
    Hex = '2fd4e1c67a2d28fced849ee1bb76e7391b93eb12'.

test(sha1_cog) :-
    sha1(`The quick brown fox jumps over the lazy cog`, O),
    hex_bytes(Hex, O),
    Hex = 'de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3'.

test(sha1_do) :-
    sha1(`The quick brown fox jumps over the lazy do`, O),
    hex_bytes(Hex, O),
    Hex = 'f2f38c31109f8a9421f301e9d554193bc4274a32'.

:- end_tests(s4c28).