Generating a MD5-Hash

Download pre-release library modules and new examples to use with Astrobe for Cortex-M3. Forum members can also upload their own source code examples.

Generating a MD5-Hash

Postby 4GlCoder » Sat Oct 27, 2012 1:12 pm

As the coming generation of ARM MCU's contains support for MD5, I thought it a good exercise to port some code over to the M3-Generation.

In short explained: MD5 generates a 32 Bytes long code that you can use to identify a block of text/code/data with. Even if only 1 bit of that block of text/code/data changed, an entirely new and different code is generated for that block.

Don't mix up this code -hashing- with encryption.. It is not intended (nor safe) to use it for that purpose.

This code is adjusted for use in Memory tight-situations, but as it processes a lot of data you need... memory...

Code: Select all
MODULE MD5;

IMPORT SYSTEM;

TYPE
  Context* = POINTER TO ContextDesc;   
  ContextDesc* = RECORD
    buf : ARRAY 4 OF INTEGER;
    bits : INTEGER;
    in : ARRAY 64 OF CHAR       
  END;
  Digest* = ARRAY 16 OF CHAR;

PROCEDURE New(VAR contrec : ContextDesc) : Context;
CONST
  cINITA = 067452301H; cINITB = 0EFCDAB89H; cINITC = 098BADCFEH; cINITD = 010325476H;
VAR
  cont : Context;
BEGIN
  SYSTEM.PUT(SYSTEM.ADR(cont), SYSTEM.ADR(contrec)); (* let cont point to contrec  *)
  cont.buf[0] := cINITA; cont.buf[1] := cINITB; cont.buf[2] := cINITC; cont.buf[3] := cINITD;
  cont.bits := 0;
  RETURN cont
END New;

PROCEDURE* Move(Src : ARRAY OF SYSTEM.BYTE; SrcOfs: INTEGER; VAR Dest : ARRAY OF SYSTEM.BYTE; DestOfs, NrOfBytes : INTEGER);
VAR
  idx : INTEGER;
BEGIN
  idx := 0;
  WHILE idx < NrOfBytes DO
    Dest[idx + DestOfs] := Src[idx + SrcOfs];
    INC(idx)
  END
END Move;

PROCEDURE* Add(a, b : INTEGER) : INTEGER;
RETURN a + b
END Add;

PROCEDURE ByteReverse(VAR inb : ARRAY OF SYSTEM.BYTE; VAR out : ARRAY OF INTEGER; longs: INTEGER);
VAR
  t, i : INTEGER;
  bytes : ARRAY 4 OF CHAR;
BEGIN
  i := 0;
  WHILE i < longs DO
    Move(inb, i * 4, bytes, 0, 4);   
    t := ORD(bytes[3]);
    t := 256*t + ORD(bytes[2]);
    t := 256*t + ORD(bytes[1]);
    t := Add(LSL(t,8), ORD(bytes[0]));  (* this avoids overflow *)
    out[i] := t;
    INC(i)
  END;
END ByteReverse;

PROCEDURE* ROTL32(val, sf : INTEGER) : INTEGER;
RETURN SYSTEM.VAL(INTEGER, SYSTEM.VAL(SET, LSL(val, sf)) + SYSTEM.VAL(SET, LSR(val, 32-sf)))
END ROTL32;

(* (B * C) + (D * (-B)) *)
PROCEDURE* F1 (B, C, D : INTEGER) : INTEGER;
RETURN SYSTEM.VAL(INTEGER, (SYSTEM.VAL(SET,B) * SYSTEM.VAL(SET,C)) + (SYSTEM.VAL(SET,D) * (-SYSTEM.VAL(SET,B))))
END F1;

PROCEDURE Step1 (VAR w : INTEGER; x, y, z, data, add, s : INTEGER);
BEGIN
(*
  w := w + F1(x,y,z)+data+add;
  w := ROTL32(w, s);
  w := w + x
 *)
  w := Add(w, F1(x,y,z)); (* this avoids overflow *)
  w := Add(w, data);
  w := Add(w, add);
  w := ROTL32(w, s);
  w := Add(w, x)
END Step1;

(* (B * D) + (C * (-D)) *)
PROCEDURE* F2 (B, C, D : INTEGER) : INTEGER;
RETURN SYSTEM.VAL(INTEGER, (SYSTEM.VAL(SET,B) * SYSTEM.VAL(SET,D)) + (SYSTEM.VAL(SET,C) * (-SYSTEM.VAL(SET,D))))
END F2;

PROCEDURE Step2 (VAR w : INTEGER; x, y, z, data, add, s : INTEGER);
BEGIN
(*
  w := w + F2(x,y,z)+data+add;
  w := ROTL32(w, s);
  w := w + x
 *)
  w := Add(w, F2(x,y,z)); (* this avoids overflow *)
  w := Add(w, data);
  w := Add(w, add);
  w := ROTL32(w, s);
  w := Add(w, x) 
END Step2;

(* B / C / D *)
PROCEDURE* F3 (B, C, D : INTEGER) : INTEGER;
RETURN SYSTEM.VAL(INTEGER, SYSTEM.VAL(SET,B) / SYSTEM.VAL(SET,C) / SYSTEM.VAL(SET,D))
END F3;

PROCEDURE Step3 (VAR w : INTEGER; x, y, z, data, add, s : INTEGER);
BEGIN
(*
  w := w + F3(x,y,z)+data+add;
  w := ROTL32(w, s);
  w := w + x
 *)
  w := Add(w, F3(x,y,z)); (* this avoids overflow *)
  w := Add(w, data);
  w := Add(w, add);
  w := ROTL32(w, s);
  w := Add(w, x)
END Step3;

(* C / (B + (-D)) *)
PROCEDURE* F4 (B, C, D : INTEGER) : INTEGER;
RETURN SYSTEM.VAL(INTEGER, SYSTEM.VAL(SET,C) / (SYSTEM.VAL(SET,B) + (-SYSTEM.VAL(SET,D))))
END F4;

PROCEDURE Step4 (VAR w : INTEGER; x, y, z, data, add, s : INTEGER);
BEGIN
(*
  w := w + F4(x,y,z)+data+add;
  w := ROTL32(w, s);
  w := w + x
 *)
  w := Add(w, F4(x,y,z)); (* this avoids overflow *)
  w := Add(w, data);
  w := Add(w, add);
  w := ROTL32(w, s);
  w := Add(w, x)
END Step4;

PROCEDURE Transform(VAR buf, in : ARRAY OF INTEGER);
VAR
  a, b, c, d : INTEGER;
BEGIN
  a := buf[0]; b := buf[1]; c := buf[2]; d := buf[3];

  (* round 1 *)
  Step1(a, b, c, d, in[ 0], 0D76AA478H,  7);
  Step1(d, a, b, c, in[ 1], 0E8C7B756H, 12);
  Step1(c, d, a, b, in[ 2], 0242070DBH, 17);
  Step1(b, c, d, a, in[ 3], 0C1BDCEEEH, 22);
  Step1(a, b, c, d, in[ 4], 0F57C0FAFH,  7);
  Step1(d, a, b, c, in[ 5], 04787C62AH, 12);
  Step1(c, d, a, b, in[ 6], 0A8304613H, 17);
  Step1(b, c, d, a, in[ 7], 0FD469501H, 22);
  Step1(a, b, c, d, in[ 8], 0698098D8H,  7);
  Step1(d, a, b, c, in[ 9], 08B44F7AFH, 12);
  Step1(c, d, a, b, in[10], 0FFFF5BB1H, 17);
  Step1(b, c, d, a, in[11], 0895CD7BEH, 22);
  Step1(a, b, c, d, in[12], 06B901122H,  7);
  Step1(d, a, b, c, in[13], 0FD987193H, 12);
  Step1(c, d, a, b, in[14], 0A679438EH, 17);
  Step1(b, c, d, a, in[15], 049B40821H, 22);
 
  (* round 2 *)
  Step2(a, b, c, d, in[ 1], 0F61E2562H,  5);
  Step2(d, a, b, c, in[ 6], 0C040B340H,  9);
  Step2(c, d, a, b, in[11], 0265E5A51H, 14);
  Step2(b, c, d, a, in[ 0], 0E9B6C7AAH, 20);
  Step2(a, b, c, d, in[ 5], 0D62F105DH,  5);
  Step2(d, a, b, c, in[10], 002441453H,  9);
  Step2(c, d, a, b, in[15], 0D8A1E681H, 14);
  Step2(b, c, d, a, in[ 4], 0E7D3FBC8H, 20);
  Step2(a, b, c, d, in[ 9], 021E1CDE6H,  5);
  Step2(d, a, b, c, in[14], 0C33707D6H,  9);
  Step2(c, d, a, b, in[ 3], 0F4D50D87H, 14);
  Step2(b, c, d, a, in[ 8], 0455A14EDH, 20);
  Step2(a, b, c, d, in[13], 0A9E3E905H,  5);
  Step2(d, a, b, c, in[ 2], 0FCEFA3F8H,  9);
  Step2(c, d, a, b, in[ 7], 0676F02D9H, 14);
  Step2(b, c, d, a, in[12], 08D2A4C8AH, 20);

  (* round 3 *)
  Step3(a, b, c, d, in[ 5], 0FFFA3942H,  4);
  Step3(d, a, b, c, in[ 8], 08771F681H, 11);
  Step3(c, d, a, b, in[11], 06D9D6122H, 16);
  Step3(b, c, d, a, in[14], 0FDE5380CH, 23);
  Step3(a, b, c, d, in[ 1], 0A4BEEA44H,  4);
  Step3(d, a, b, c, in[ 4], 04BDECFA9H, 11);
  Step3(c, d, a, b, in[ 7], 0F6BB4B60H, 16);
  Step3(b, c, d, a, in[10], 0BEBFBC70H, 23);
  Step3(a, b, c, d, in[13], 0289B7EC6H,  4);
  Step3(d, a, b, c, in[ 0], 0EAA127FAH, 11);
  Step3(c, d, a, b, in[ 3], 0D4EF3085H, 16);
  Step3(b, c, d, a, in[ 6], 004881D05H, 23);
  Step3(a, b, c, d, in[ 9], 0D9D4D039H,  4);
  Step3(d, a, b, c, in[12], 0E6DB99E5H, 11);
  Step3(c, d, a, b, in[15], 01FA27CF8H, 16);
  Step3(b, c, d, a, in[ 2], 0C4AC5665H, 23);

  (* round 4 *)
  Step4(a, b, c, d, in[ 0], 0F4292244H,  6);
  Step4(d, a, b, c, in[ 7], 0432AFF97H, 10);
  Step4(c, d, a, b, in[14], 0AB9423A7H, 15);
  Step4(b, c, d, a, in[ 5], 0FC93A039H, 21);
  Step4(a, b, c, d, in[12], 0655B59C3H,  6);
  Step4(d, a, b, c, in[ 3], 08F0CCC92H, 10);
  Step4(c, d, a, b, in[10], 0FFEFF47DH, 15);
  Step4(b, c, d, a, in[ 1], 085845DD1H, 21);
  Step4(a, b, c, d, in[ 8], 06FA87E4FH,  6);
  Step4(d, a, b, c, in[15], 0FE2CE6E0H, 10);
  Step4(c, d, a, b, in[ 6], 0A3014314H, 15);
  Step4(b, c, d, a, in[13], 04E0811A1H, 21);
  Step4(a, b, c, d, in[ 4], 0F7537E82H,  6);
  Step4(d, a, b, c, in[11], 0BD3AF235H, 10);
  Step4(c, d, a, b, in[ 2], 02AD7D2BBH, 15);
  Step4(b, c, d, a, in[ 9], 0EB86D391H, 21);

  buf[0] := Add(buf[0], a); (* this avoids overflow *)
  buf[1] := Add(buf[1], b);
  buf[2] := Add(buf[2], c);
  buf[3] := Add(buf[3], d)
END Transform;

(* Continues an MD5 message-digest operation, processing another message block
   and updating the context *)
PROCEDURE WriteBytes*(context:  Context; buf : ARRAY OF CHAR;  len : INTEGER);
VAR
  in : ARRAY 16 OF INTEGER;
  beg, t : INTEGER;
  done  : BOOLEAN;
BEGIN
  beg := 0; t := context.bits;
  context.bits := t + len*8;
  t := (t DIV 8) MOD 64;
  done := FALSE;
  IF t > 0 THEN
    t := 64 - t;
    IF len < t THEN
      Move(buf, beg, context.in, 64-t, len);
      done := TRUE
    ELSE
      Move(buf, beg, context.in, 64-t, t);
      ByteReverse(context.in, in, 16);
      Transform(context.buf, in);
      beg := beg + t; len := len - t
    END
  END;
  IF ~done THEN
    WHILE len >= 64 DO
      Move(buf, beg, context.in, 0, 64);
      ByteReverse(context.in, in, 16);
      Transform(context.buf, in);
      INC(beg, 64); DEC(len, 64)
    END;
    IF len > 0 THEN
      Move(buf, beg, context.in, 0, len)
    END
  END
END WriteBytes;

(* End a MD5 Message digest operation by flushing the message digest *)
PROCEDURE Close*(context : Context; VAR digest : Digest);
VAR
  in : ARRAY 16 OF INTEGER;
  beg, i, count : INTEGER;
BEGIN
  count := (context.bits DIV 8) MOD 64;
  beg := count;
  context.in[beg] := CHR(128); INC(beg);
  count := 64-1-count;
  IF count < 8 THEN
    i := 0;
    WHILE i < count DO
      context.in[ beg + i] := 0X; INC(i)
    END;
    ByteReverse(context.in, in, 16);
    Transform(context.buf, in);
    i := 0;
    WHILE i < 56 DO
      context.in[i] := 0X; INC(i)
    END
  ELSE
    i := 0;
    WHILE i < (count - 8) DO
      context.in[beg + i] := 0X; INC(i)
    END
  END;
  ByteReverse(context.in, in, 14);
  in[14] := context.bits; in[15] := 0;
  Transform(context.buf, in);
  ByteReverse(context.buf, in, 4);
  Move(in, 0, digest, 0, 16)
END Close;

PROCEDURE* HexDigit(i : INTEGER):CHAR;
VAR
  retc : CHAR;
BEGIN
  IF i < 10 THEN
    retc := CHR(ORD("0") + i)
  ELSE
    retc := CHR(ORD("a") + i - 10)
  END;
  RETURN retc
END HexDigit;

(* Convert the digest into an hexadecimal string *)
PROCEDURE ToString*(digest : Digest; VAR str : ARRAY OF CHAR);
VAR
  i : INTEGER;
BEGIN
  FOR i := 0 TO 15 DO
    str[2*i] := HexDigit(ORD(digest[i]) DIV 16);
    str[2*i+1] := HexDigit(ORD(digest[i]) MOD 16)
  END;
  IF LEN(str) > 32 THEN
    str[32] := 0X
  END;
END ToString;

(* produce standard hash *)
PROCEDURE Hash*(inbuf: ARRAY OF CHAR; inlength : INTEGER; VAR outa : ARRAY OF CHAR) : BOOLEAN;
VAR
  cont   : Context;
  contrec : ContextDesc;
  digest : Digest;
  retval : BOOLEAN;
BEGIN
  retval := LEN(outa) >= 32;  (* enough space for complete MD5-Hash? *)
  IF retval THEN
    cont := New(contrec); 
    WriteBytes(cont, inbuf, inlength);
    Close(cont, digest);
    ToString(digest, outa)
  ELSIF LEN(outa) > 0 THEN
    outa[0] := 0X   
  END;
  RETURN retval
END Hash;

END MD5.


As this is specifically written for the Astrobe environment, in comment-section below you see some values and expected results

Code: Select all
MODULE TestMD5;

IMPORT Main, MD5, Serial, Strings;

(* test vectors taken from the RFC document
Test values:
""                  D4 1D 8C D9 8F 00 B2 04  E9 80 09 98 EC F8 42 7E
"a"                 0C C1 75 B9 C0 F1 B6 A8  31 C3 99 E2 69 77 26 61
"abc"               90 01 50 98 3C D2 4F B0  D6 96 3F 7D 28 E1 7F 72
"message digest"    F9 6B 69 7D 7C B7 93 8D  52 5A 2F 31 AA F1 61 D0
"12345678901234567890123456789012345678901234567890123456789012345678901234567890"
                    57 ED F4 A2 2B E3 C9 55  AC 49 DA 2E 21 07 B6 7A
*)
PROCEDURE WriteString(aoc : ARRAY OF CHAR);
VAR
  idx, slen : INTEGER;
BEGIN
  slen := Strings.Length(aoc);
  idx := 0;
  WHILE idx < slen DO
    Serial.PutCh(aoc[idx]);
    INC(idx)
  END
END WriteString;

PROCEDURE WriteCRLF;
BEGIN
  Serial.PutCh(0DX); Serial.PutCh(0AX)
END WriteCRLF;

PROCEDURE WriteLine(aoc : ARRAY OF CHAR);
BEGIN
  WriteString(aoc); WriteCRLF
END WriteLine;
 
PROCEDURE OneTest(testa : ARRAY OF CHAR);
VAR
  slen : INTEGER;
  aoc : ARRAY 36 OF CHAR;
BEGIN
  slen := Strings.Length(testa);
  IF MD5.Hash(testa, slen, aoc) THEN
    WriteString("'"); WriteString(testa); WriteString("' -> "); WriteLine(aoc)
  ELSE
    WriteLine("Buffer is too short..")
  END
END OneTest;

(* The Astrobe Compiler can't handle text-constants over 60 long, so double it within this procedure *)
PROCEDURE LongTest;
CONST
  halfstr = "1234567890123456789012345678901234567890";   (* 40 long *)
VAR
  tolongforCompiler : ARRAY 84 OF CHAR;
BEGIN
  Strings.Copy(halfstr, tolongforCompiler);
  Strings.Append(halfstr, tolongforCompiler); 
  OneTest(tolongforCompiler)
END LongTest;
 
PROCEDURE AllTests;
BEGIN
  OneTest("");
  OneTest("a");
  OneTest("abc");
  OneTest("message digest");
  LongTest
END AllTests;

BEGIN
  AllTests
END TestMD5.


Note: this code also works in LPC2000 release.

Cheers., 0265E5A51H, 14);
Step2(b, c, d, a, inHash(testa, slen, aoc) THEN
WriteString(
4GlCoder
 
Posts: 27
Joined: Fri Jul 22, 2011 2:47 pm

Re: Generating a MD5-Hash

Postby Alexander Shiryaev » Mon Oct 29, 2012 2:55 am

There is my translation.

Code: Select all
MODULE MD5;   (** portable *) (* ejz  *)
   IMPORT SYSTEM;

(* ETH Oberon, Copyright 2001 ETH Zuerich Institut fuer Computersysteme, ETH Zentrum, CH-8092 Zuerich.
Refer to the "General ETH Oberon System Source License" contract available at: http://www.oberon.ethz.ch/ *)

(** The MD5 Message-Digest Algorithm (RFC1321)

The algorithm takes as input a message of arbitrary length and produces
as output a 128-bit "fingerprint" or "message digest" of the input. It is
conjectured that it is computationally infeasible to produce two messages
having the same message digest, or to produce any message having a
given prespecified target message digest. The MD5 algorithm is intended
for digital signature applications, where a large file must be "compressed"
in a secure manner before being encrypted with a private (secret) key
under a public-key cryptosystem such as RSA. *)

   TYPE
      Context = RECORD
         buf: ARRAY 4 OF INTEGER;
         bits: INTEGER;
         in: ARRAY 64 OF CHAR
      END;
      Digest* = ARRAY 16 OF CHAR;

(** Begin an MD5 operation, with a new context. *)
   PROCEDURE* New*(VAR cont: Context);
   BEGIN
      cont.buf[0] := 067452301H;

      (*
      cont.buf[1] := SHORT(0EFCDAB89H);
      cont.buf[2] := SHORT(098BADCFEH);
      *)
      cont.buf[1] := 0EFCDAB89H;
      cont.buf[2] := 098BADCFEH;

      cont.buf[3] := 010325476H;
      cont.bits := 0
   END New;

   PROCEDURE* ByteReverse(VAR in: ARRAY OF SYSTEM.BYTE; VAR out: ARRAY OF INTEGER; longs: INTEGER);
      VAR
         adr: INTEGER; t, i: INTEGER; tmp: INTEGER;
         bytes: ARRAY 4 OF CHAR;
   BEGIN
      adr := SYSTEM.ADR(in[0]); i := 0;
      WHILE i < longs DO
         (* SYSTEM.MOVE(adr, SYSTEM.ADR(bytes[0]), 4); *)
         SYSTEM.GET(adr, tmp); SYSTEM.PUT(SYSTEM.ADR(bytes), tmp);
         t := ORD(bytes[3]);
         t := 256*t + ORD(bytes[2]);
         t := 256*t + ORD(bytes[1]);
         t := 256*t + ORD(bytes[0]);
         out[i] := t;
         INC(adr, 4); INC(i)
      END
   END ByteReverse;

   PROCEDURE* F1(x, y, z: INTEGER): INTEGER;
   BEGIN
      RETURN SYSTEM.VAL(INTEGER, (SYSTEM.VAL(SET, x)*SYSTEM.VAL(SET, y)) + ((-SYSTEM.VAL(SET, x))*SYSTEM.VAL(SET, z)))
   END F1;

   PROCEDURE* F2(x, y, z: INTEGER): INTEGER;
   BEGIN
      RETURN SYSTEM.VAL(INTEGER, (SYSTEM.VAL(SET, x)*SYSTEM.VAL(SET, z)) + (SYSTEM.VAL(SET, y)*(-SYSTEM.VAL(SET, z))))
   END F2;

   PROCEDURE* F3(x, y, z: INTEGER): INTEGER;
   BEGIN
      RETURN SYSTEM.VAL(INTEGER, SYSTEM.VAL(SET, x) / SYSTEM.VAL(SET, y) / SYSTEM.VAL(SET, z))
   END F3;

   PROCEDURE* F4(x, y, z: INTEGER): INTEGER;
   BEGIN
      RETURN SYSTEM.VAL(INTEGER, SYSTEM.VAL(SET, y) / (SYSTEM.VAL(SET, x)+(-SYSTEM.VAL(SET, z))))
   END F4;

   PROCEDURE STEP1(VAR w: INTEGER; x, y, z, data: INTEGER; add: INTEGER;  s: INTEGER);
   BEGIN
      w := w+F1(x, y, z)+data+add;
      w := ROR(w, -s);
      w := w + x
   END STEP1;

   PROCEDURE STEP2(VAR w: INTEGER; x, y, z, data: INTEGER; add: INTEGER; s: INTEGER);
   BEGIN
      w := w+F2(x, y, z)+data+add;
      w := ROR(w, -s);
      w := w + x
   END STEP2;

   PROCEDURE STEP3(VAR w: INTEGER; x, y, z, data: INTEGER; add: INTEGER; s: INTEGER);
   BEGIN
      w := w+F3(x, y, z)+data+add;
      w := ROR(w, -s);
      w := w + x
   END STEP3;

   PROCEDURE STEP4(VAR w: INTEGER; x, y, z, data: INTEGER; add: INTEGER; s: INTEGER);
   BEGIN
      w := w+F4(x, y, z)+data+add;
      w := ROR(w, -s);
      w := w + x
   END STEP4;

   PROCEDURE Transform(VAR buf, in: ARRAY OF INTEGER);
      VAR a, b, c, d: INTEGER;
   BEGIN
      a := buf[0]; b := buf[1]; c := buf[2]; d := buf[3];

      STEP1(a, b, c, d, in[0],0D76AA478H, 7);
      STEP1(d, a, b, c, in[1],0E8C7B756H, 12);
      STEP1(c, d, a, b, in[2],0242070DBH, 17);
      STEP1(b, c, d, a, in[3],0C1BDCEEEH, 22);
      STEP1(a, b, c, d, in[4],0F57C0FAFH, 7);
      STEP1(d, a, b, c, in[5],04787C62AH, 12);
      STEP1(c, d, a, b, in[6],0A8304613H, 17);
      STEP1(b, c, d, a, in[7],0FD469501H, 22);
      STEP1(a, b, c, d, in[8],0698098D8H, 7);
      STEP1(d, a, b, c, in[9],08B44F7AFH, 12);
      STEP1(c, d, a, b, in[10],0FFFF5BB1H, 17);
      STEP1(b, c, d, a, in[11],0895CD7BEH, 22);
      STEP1(a, b, c, d, in[12],06B901122H, 7);
      STEP1(d, a, b, c, in[13],0FD987193H, 12);
      STEP1(c, d, a, b, in[14],0A679438EH, 17);
      STEP1(b, c, d, a, in[15],049B40821H, 22);

      STEP2(a, b, c, d, in[1],0F61E2562H, 5);
      STEP2(d, a, b, c, in[6],0C040B340H, 9);
      STEP2(c, d, a, b, in[11],0265E5A51H, 14);
      STEP2(b, c, d, a, in[0],0E9B6C7AAH, 20);
      STEP2(a, b, c, d, in[5],0D62F105DH, 5);
      STEP2(d, a, b, c, in[10],02441453H, 9);
      STEP2(c, d, a, b, in[15],0D8A1E681H, 14);
      STEP2(b, c, d, a, in[4],0E7D3FBC8H, 20);
      STEP2(a, b, c, d, in[9],021E1CDE6H, 5);
      STEP2(d, a, b, c, in[14],0C33707D6H, 9);
      STEP2(c, d, a, b, in[3],0F4D50D87H, 14);
      STEP2(b, c, d, a, in[8],0455A14EDH, 20);
      STEP2(a, b, c, d, in[13],0A9E3E905H, 5);
      STEP2(d, a, b, c, in[2],0FCEFA3F8H, 9);
      STEP2(c, d, a, b, in[7],0676F02D9H, 14);
      STEP2(b, c, d, a, in[12],08D2A4C8AH, 20);

      STEP3(a, b, c, d, in[5],0FFFA3942H, 4);
      STEP3(d, a, b, c, in[8],08771F681H, 11);
      STEP3(c, d, a, b, in[11],06D9D6122H, 16);
      STEP3(b, c, d, a, in[14],0FDE5380CH, 23);
      STEP3(a, b, c, d, in[1],0A4BEEA44H, 4);
      STEP3(d, a, b, c, in[4],04BDECFA9H, 11);
      STEP3(c, d, a, b, in[7],0F6BB4B60H, 16);
      STEP3(b, c, d, a, in[10],0BEBFBC70H, 23);
      STEP3(a, b, c, d, in[13],0289B7EC6H, 4);
      STEP3(d, a, b, c, in[0],0EAA127FAH, 11);
      STEP3(c, d, a, b, in[3],0D4EF3085H, 16);
      STEP3(b, c, d, a, in[6],04881D05H, 23);
      STEP3(a, b, c, d, in[9],0D9D4D039H, 4);
      STEP3(d, a, b, c, in[12],0E6DB99E5H, 11);
      STEP3(c, d, a, b, in[15],01FA27CF8H, 16);
      STEP3(b, c, d, a, in[2],0C4AC5665H, 23);

      STEP4(a, b, c, d, in[0],0F4292244H, 6);
      STEP4(d, a, b, c, in[7],0432AFF97H, 10);
      STEP4(c, d, a, b, in[14],0AB9423A7H, 15);
      STEP4(b, c, d, a, in[5],0FC93A039H, 21);
      STEP4(a, b, c, d, in[12],0655B59C3H, 6);
      STEP4(d, a, b, c, in[3],08F0CCC92H, 10);
      STEP4(c, d, a, b, in[10],0FFEFF47DH, 15);
      STEP4(b, c, d, a, in[1],085845DD1H, 21);
      STEP4(a, b, c, d, in[8],06FA87E4FH, 6);
      STEP4(d, a, b, c, in[15],0FE2CE6E0H, 10);
      STEP4(c, d, a, b, in[6],0A3014314H, 15);
      STEP4(b, c, d, a, in[13],04E0811A1H, 21);
      STEP4(a, b, c, d, in[4],0F7537E82H, 6);
      STEP4(d, a, b, c, in[11], 0BD3AF235H, 10);
      STEP4(c, d, a, b, in[2],02AD7D2BBH, 15);
      STEP4(b, c, d, a, in[9],0EB86D391H, 21);

      buf[0] := buf[0] + a; buf[1] := buf[1] + b;
      buf[2] := buf[2] + c; buf[3] := buf[3] + d
   END Transform;

(** Continues an MD5 message-digest operation, processing another
   message block, and updating the context. *)
   PROCEDURE Write*(VAR context: Context; ch: CHAR);
      VAR
         in: ARRAY 16 OF INTEGER;
         t, len: INTEGER;
         doReturn: BOOLEAN;
   BEGIN
      t := context.bits; len := 1;
      context.bits := t + 8;
      t := (t DIV 8) MOD 64;
      doReturn := FALSE;
      IF t > 0 THEN
         t := 64-t;
         IF 1 < t THEN
            context.in[64-t] := ch;
            doReturn := TRUE
         END;
         IF ~doReturn THEN
            ASSERT(len = 1);
            context.in[64-t] := ch;
            ByteReverse(context.in, in, 16);
            Transform(context.buf, in);
            len := len - t
         END
      END;
      IF ~doReturn THEN
         IF len > 0 THEN
            context.in[0] := ch
         END
      END
   END Write;

   PROCEDURE* MOVE (src, dst, len: INTEGER);
      VAR t: CHAR;
   BEGIN
      WHILE len > 0 DO
         SYSTEM.GET(src, t); INC(src);
         SYSTEM.PUT(dst, t); INC(dst);
         DEC(len)
      END
   END MOVE;

(** Continues an MD5 message-digest operation, processing another
   message block, and updating the context. *)
   PROCEDURE WriteBytes*(VAR context: Context; buf: ARRAY OF CHAR; len: INTEGER);
      VAR
         in: ARRAY 16 OF INTEGER;
         beg, t: INTEGER;
         continue: BOOLEAN;
   BEGIN
      beg := 0; t := context.bits;
      context.bits := t + len*8;
      t := (t DIV 8) MOD 64;
      continue := TRUE;
      IF t > 0 THEN
         t := 64-t;
         IF len < t THEN
            MOVE(SYSTEM.ADR(buf[beg]), SYSTEM.ADR(context.in[64-t]), len);
            continue := FALSE
         ELSE
            MOVE(SYSTEM.ADR(buf[beg]), SYSTEM.ADR(context.in[64-t]), t);
            ByteReverse(context.in, in, 16);
            Transform(context.buf, in);
            beg := beg + t; len := len - t
         END
      END;
      IF continue THEN
         WHILE len >= 64 DO
            MOVE(SYSTEM.ADR(buf[beg]), SYSTEM.ADR(context.in[0]), 64);
            ByteReverse(context.in, in, 16);
            Transform(context.buf, in);
            INC(beg, 64); DEC(len, 64)
         END;
         IF len > 0 THEN
            MOVE(SYSTEM.ADR(buf[beg]), SYSTEM.ADR(context.in[0]), len)
         END
      END
   END WriteBytes;

(** Ends an MD5 message-digest operation, writing the message digest. *)
   PROCEDURE Close*(VAR context: Context; VAR digest: Digest);
      VAR
         in: ARRAY 16 OF INTEGER;
         beg, i, count: INTEGER;
         tmp: INTEGER;
   BEGIN
      count := (context.bits DIV 8) MOD 64;
      beg := count;
      context.in[beg] := CHR(128); INC(beg);
      count := 64-1-count;
      IF count < 8 THEN
         i := 0;
         WHILE i < count DO
            context.in[beg+i] := 0X; INC(i)
         END;
         ByteReverse(context.in, in, 16);
         Transform(context.buf, in);
         i := 0;
         WHILE i < 56 DO
            context.in[i] := 0X; INC(i)
         END
      ELSE
         i := 0;
         WHILE i < (count-8) DO
            context.in[beg+i] := 0X; INC(i)
         END
      END;
      ByteReverse(context.in, in, 14);
      in[14] := context.bits; in[15] := 0;
      Transform(context.buf, in);
      ByteReverse(context.buf, in, 4);
      (* SYSTEM.MOVE(SYSTEM.ADR(in[0]), SYSTEM.ADR(digest[0]), 16) *)
      SYSTEM.GET(SYSTEM.ADR(in), tmp); SYSTEM.PUT(SYSTEM.ADR(digest), tmp);
      SYSTEM.GET(SYSTEM.ADR(in) + 4, tmp); SYSTEM.PUT(SYSTEM.ADR(digest) + 4, tmp);
      SYSTEM.GET(SYSTEM.ADR(in) + 8, tmp); SYSTEM.PUT(SYSTEM.ADR(digest) + 8, tmp);
      SYSTEM.GET(SYSTEM.ADR(in) + 12, tmp); SYSTEM.PUT(SYSTEM.ADR(digest) + 12, tmp)
   END Close;

   PROCEDURE* HexDigit(i: INTEGER): CHAR;
      VAR res: CHAR;
   BEGIN
      IF i < 10 THEN
         res := CHR(48+i)
      ELSE
         res := CHR(87+i)
      END;
      RETURN res
   END HexDigit;

(** Convert the digest into an hexadecimal string. *)
   PROCEDURE ToString*(VAR digest: Digest; VAR str: ARRAY OF CHAR);
      VAR i: INTEGER;
   BEGIN
      FOR i := 0 TO 15 DO
         str[2*i] := HexDigit(ORD(digest[i]) DIV 16);
         str[2*i+1] := HexDigit(ORD(digest[i]) MOD 16)
      END;
      str[32] := 0X
   END ToString;

END MD5.
Last edited by Alexander Shiryaev on Mon Oct 29, 2012 1:50 pm, edited 1 time in total.
Alexander Shiryaev
 
Posts: 19
Joined: Mon Apr 04, 2011 7:20 pm
Location: Russia

Re: Generating a MD5-Hash

Postby cfbsoftware » Mon Oct 29, 2012 11:34 am

Thank you both for your examples. I also would have used ROR and would have noted that Astrobe ignores overflows as implemented by Alexander. However, I believe that 4GLCoder deliberatly didn't use NEW to avoid exhausting the heap (there is no automatic garbage collection). This should be less of a problem in v4.3 when DISPOSE can be used to reclaim dynamic memory.

I have a couple of additional observations:

1. Astrobe v4.2 has a built-in procedure BITS. Also, in both systems, ORD can be used to type-transfer a SET to an INTEGER. Consequently, instead of:

Code: Select all
RETURN SYSTEM.VAL(INTEGER, (SYSTEM.VAL(SET, x)*SYSTEM.VAL(SET, y)) + ((-SYSTEM.VAL(SET, x))*SYSTEM.VAL(SET, z)))


you can now write:

Code: Select all
RETURN ORD((BITS(x) * BITS(y)) + (-BITS(x) * BITS(z)))


Both are efficient as each other, generating an identical set of six instructions:
Code: Select all
EA0B080AH  and      r8,r11,r10
EA6F070BH  mvn      r7,r11
EA070709H  and      r7,r7,r9
EA480807H  orr      r8,r8,r7
EA4F0B08H  mov      r11,r8
4770H      bx       lr


2. For a while now we have been considering implementing some more SYSTEM functions to improve the efficiency of some commonly used operations. SYSTEM.MOVE which is present in many other implementations of Oberon would have been useful in this example.

Also we could exploit some of the additional instructions that have no direct Oberon language equivalents. Such a function would be SYSTEM.REV. This could use the Cortex-M3 REV instruction to reverse the byte order of a 32-bit integer in a single operation.

As a result of this example these ideas have now moved closer to the top of the list of things to do.
cfbsoftware
Site Admin
 
Posts: 341
Joined: Fri Dec 31, 2010 12:30 pm

Re: Generating a MD5-Hash

Postby Alexander Shiryaev » Mon Oct 29, 2012 2:04 pm

However, I believe that 4GLCoder deliberatly didn't use NEW to avoid exhausting the heap (there is no automatic garbage collection).


POINTER TO RECORD not required here. Context may be of RECORD type. I updated my previous post.

As you can see, Context not marked for export, but the following test program compiled ok:
Code: Select all
MODULE MD5Test;

   IMPORT Main, MD5, Out;

   PROCEDURE MD5String (s: ARRAY OF CHAR; len: INTEGER; VAR hash: ARRAY OF CHAR);
      VAR c: MD5.Context;
         digest: MD5.Digest;
   BEGIN
      MD5.New(c);
      MD5.WriteBytes(c, s, len);
      MD5.Close(c, digest);
      MD5.ToString(digest, hash)
   END MD5String;

   PROCEDURE Do;
      VAR c: MD5.Context;
         digest: MD5.Digest;
         s: ARRAY 33 OF CHAR;
   BEGIN
      MD5.New(c);
      MD5.Close(c, digest);
      MD5.ToString(digest, s);
      Out.String(s); Out.Ln;

      MD5String("", 0, s); Out.String(s); Out.Ln;
      MD5String("ABCD", 4, s); Out.String(s); Out.Ln;
      MD5String("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz01", 26+26+2, s); Out.String(s); Out.Ln;
   END Do;

BEGIN Do
END MD5Test.

There is mistake in compiler (Astrobe LPC2000 4.0.2).
Alexander Shiryaev
 
Posts: 19
Joined: Mon Apr 04, 2011 7:20 pm
Location: Russia


Return to Cortex-M3

cron