MD5: RFC 1321 を実装してみる

RFC 1321 (The MD5 Message-Digest Algorithm) を見ながら実装してみた。

以下を念頭に置いています

+ ビット単位の入力は考慮しない
+ コンパクトなものにする
+ 凝ったことはあまりしない


# データの種類

データのバイト列は、リトル・エンディアンとして扱います。

| 種類 | ビット数 | バイト数 | ワード数 | シンボル |
|:-:|:-:|:-:|:-:|:-:|
| ワード | 32 | 4 | 1 | |
| ブロック | 512 | 64 | 16 | X[&#x20;] |
| ダイジェスト値 | 128 | 16 | 4 | S[&#x20;] または A,B,C,D |

<details><summary>ダイジェスト値 A,B,C,D は配列 S と等しいものとします。</summary><div>

```c++:例&#x3a;C++
uint32_t &A = S[0];
uint32_t &B = S[1];
uint32_t &C = S[2];
uint32_t &D = S[3];
```

</div></details>


# 入力データと入力の拡張

入力データの後続に、入力の拡張として、「1ビットの"1"」と「入力のビット数」が追加されます。また、ダイジェスト値の計算は、ブロック単位で行われるので、全体がブロック単位となるように "0" で埋めます。

追加されるバイト列データの並びは以下になります。

| バイト数 | データ |
|:-:|:-:|
| 1 | 0x80 |
| 0 〜 55 | 0x00 |
| 8 | 入力のビット数（64ビット） |


# ブロック単位の計算

1ブロックに対して、64要素のテーブルを使って計算します。テーブルは

```c:C
T[i] = int(abs(sin(i)) * 4294967296);  /* i はラジアンで 1 から 64 */
```

とされています。i が 1 からだと都合が悪いので、実際のプログラムでは

```c:C
T[i] = int(abs(sin(i+1)) * 4294967296);  /* i は 0 から 63 */
```

にします。T に対して、4種類の関数と16ワードで、計64回の計算を実行します。

4種類の関数は

| 関数 | 計算 |
|:-:|:-:|
| F(x, y, z) | (y & x) &#x7c; (z & ~x) |
| G(x, y, z) | (x & z) &#x7c; (y & ~z) |
| H(x, y, z) | x ^ y ^ z |
| I(x, y, z) | y ^ (x &#x7c; ~z) |

となっていて、F,G,H,I を総じて Q とします。

これと、32ビット左ローテート(大抵のCPUでは1命令)

```c:C
uint32_t RotateLeft(uint32_t v, int n)
{
  return (v << n) | (v >> (32 - n));
}
```

が使われます。


**ダイジェスト値の初期値**

ダイジェスト値 A,B,C,D の初期値は

```c:
A = 0x67452301
B = 0xefcdab89
C = 0x98badcfe
D = 0x10325476
```

となっています。


## ダイジェスト値の更新

テーブル T[i] の i を 0 から順に 63 まで使って、ダイジェスト値の更新します。

一回の計算は

```c:Round
// a,b,c,d,k,s および Q は i に応じて決められている
// S[a],S[b],S[c],S[d] は A,B,C,D をシャッフルしたものに相当
S[a] = S[b] + RotateLeft(X[k] + T[i] + S[a] + Q(S[b], S[c], S[d]), s)
```

として更新されます。

## T[i] と各要素の対応

<details><summary>i と Q,a,b,c,d,k,s の対応表（長いので折りたたみ）</summary><div>

| i  | Q | a | b | c | d | k  | s  |
|:--:|:-:|:-:|:-:|:-:|:-:|:--:|:--:|
| 0  | F | 0 | 1 | 2 | 3 | 0  | 7  |
| 1  | F | 3 | 0 | 1 | 2 | 1  | 12 |
| 2  | F | 2 | 3 | 0 | 1 | 2  | 17 |
| 3  | F | 1 | 2 | 3 | 0 | 3  | 22 |
| 4  | F | 0 | 1 | 2 | 3 | 4  | 7  |
| 5  | F | 3 | 0 | 1 | 2 | 5  | 12 |
| 6  | F | 2 | 3 | 0 | 1 | 6  | 17 |
| 7  | F | 1 | 2 | 3 | 0 | 7  | 22 |
| 8  | F | 0 | 1 | 2 | 3 | 8  | 7  |
| 9  | F | 3 | 0 | 1 | 2 | 9  | 12 |
| 10 | F | 2 | 3 | 0 | 1 | 10 | 17 |
| 11 | F | 1 | 2 | 3 | 0 | 11 | 22 |
| 12 | F | 0 | 1 | 2 | 3 | 12 | 7  |
| 13 | F | 3 | 0 | 1 | 2 | 13 | 12 |
| 14 | F | 2 | 3 | 0 | 1 | 14 | 17 |
| 15 | F | 1 | 2 | 3 | 0 | 15 | 22 |
| 16 | G | 0 | 1 | 2 | 3 | 1  | 5  |
| 17 | G | 3 | 0 | 1 | 2 | 6  | 9  |
| 18 | G | 2 | 3 | 0 | 1 | 11 | 14 |
| 19 | G | 1 | 2 | 3 | 0 | 0  | 20 |
| 20 | G | 0 | 1 | 2 | 3 | 5  | 5  |
| 21 | G | 3 | 0 | 1 | 2 | 10 | 9  |
| 22 | G | 2 | 3 | 0 | 1 | 15 | 14 |
| 23 | G | 1 | 2 | 3 | 0 | 4  | 20 |
| 24 | G | 0 | 1 | 2 | 3 | 9  | 5  |
| 25 | G | 3 | 0 | 1 | 2 | 14 | 9  |
| 26 | G | 2 | 3 | 0 | 1 | 3  | 14 |
| 27 | G | 1 | 2 | 3 | 0 | 8  | 20 |
| 28 | G | 0 | 1 | 2 | 3 | 13 | 5  |
| 29 | G | 3 | 0 | 1 | 2 | 2  | 9  |
| 30 | G | 2 | 3 | 0 | 1 | 7  | 14 |
| 31 | G | 1 | 2 | 3 | 0 | 12 | 20 |
| 32 | H | 0 | 1 | 2 | 3 | 5  | 4  |
| 33 | H | 3 | 0 | 1 | 2 | 8  | 11 |
| 34 | H | 2 | 3 | 0 | 1 | 11 | 16 |
| 35 | H | 1 | 2 | 3 | 0 | 14 | 23 |
| 36 | H | 0 | 1 | 2 | 3 | 1  | 4  |
| 37 | H | 3 | 0 | 1 | 2 | 4  | 11 |
| 38 | H | 2 | 3 | 0 | 1 | 7  | 16 |
| 39 | H | 1 | 2 | 3 | 0 | 10 | 23 |
| 40 | H | 0 | 1 | 2 | 3 | 13 | 4  |
| 41 | H | 3 | 0 | 1 | 2 | 0  | 11 |
| 42 | H | 2 | 3 | 0 | 1 | 3  | 16 |
| 43 | H | 1 | 2 | 3 | 0 | 6  | 23 |
| 44 | H | 0 | 1 | 2 | 3 | 9  | 4  |
| 45 | H | 3 | 0 | 1 | 2 | 12 | 11 |
| 46 | H | 2 | 3 | 0 | 1 | 15 | 16 |
| 47 | H | 1 | 2 | 3 | 0 | 2  | 23 |
| 48 | I | 0 | 1 | 2 | 3 | 0  | 6  |
| 49 | I | 3 | 0 | 1 | 2 | 7  | 10 |
| 50 | I | 2 | 3 | 0 | 1 | 14 | 15 |
| 51 | I | 1 | 2 | 3 | 0 | 5  | 21 |
| 52 | I | 0 | 1 | 2 | 3 | 12 | 6  |
| 53 | I | 3 | 0 | 1 | 2 | 3  | 10 |
| 54 | I | 2 | 3 | 0 | 1 | 10 | 15 |
| 55 | I | 1 | 2 | 3 | 0 | 1  | 21 |
| 56 | I | 0 | 1 | 2 | 3 | 8  | 6  |
| 57 | I | 3 | 0 | 1 | 2 | 15 | 10 |
| 58 | I | 2 | 3 | 0 | 1 | 6  | 15 |
| 59 | I | 1 | 2 | 3 | 0 | 13 | 21 |
| 60 | I | 0 | 1 | 2 | 3 | 4  | 6  |
| 61 | I | 3 | 0 | 1 | 2 | 11 | 10 |
| 62 | I | 2 | 3 | 0 | 1 | 2  | 15 |
| 63 | I | 1 | 2 | 3 | 0 | 9  | 21 |

</div></details>

### i と Q（関数）の対応

| i の範囲 | i >> 4 | Q |
|:--------:|:------:|:-:|
| 00 〜 15 | 0      | F |
| 16 〜 31 | 1      | G |
| 32 〜 47 | 2      | H |
| 48 〜 63 | 3      | I |

### i と a,b,c,d（ダイジェスト値）の対応

| i    | a | b | c | d | 備考      |
|:----:|:-:|:-:|:-:|:-:|:---------:|
| 4n+0 | 0 | 1 | 2 | 3 | a = 0 % 4 |
| 4n+1 | 3 | 0 | 1 | 2 | a = 3 % 4 |
| 4n+2 | 2 | 3 | 0 | 1 | a = 6 % 4 |
| 4n+3 | 1 | 2 | 3 | 0 | a = 9 % 4 |

### i と k（ブロック）の対応

| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|:----:|--:|--:|---:|---:|---:|---:|---:|---:|
| **0x00** | 0 | 1 |  2 |  3 |  4 |  5 |  6 |  7 |
| **0x10** | 1 | 6 | 11 |  0 |  5 | 10 | 15 |  4 |
| **0x20** | 5 | 8 | 11 | 14 |  1 |  4 |  7 | 10 |
| **0x30** | 0 | 7 | 14 |  5 | 12 |  3 | 10 |  1 |

| i | 8 | 9 | A | B | C | D | E | F |
|:----:|---:|---:|---:|---:|---:|---:|---:|---:|
| **0x00** |  8 |  9 | 10 | 11 | 12 | 13 | 14 | 15 |
| **0x10** |  9 | 14 |  3 |  8 | 13 |  2 |  7 | 12 |
| **0x20** | 13 |  0 |  3 |  6 |  9 | 12 | 15 |  2 |
| **0x30** |  8 | 15 |  6 | 13 |  4 | 11 |  2 |  9 |

<sub></sub>

| i の範囲 | k |
|:-:|:-:|
| 0x00 〜 0x0f | ((i * 1) + 0) % 16 |
| 0x10 〜 0x1f | ((i * 5) + 1) % 16 |
| 0x20 〜 0x2f | ((i * 3) + 5) % 16 |
| 0x30 〜 0x3f | ((i * 7) + 0) % 16 |


### i と s（ローテート ビット数）の対応

| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|:----:|--:|---:|---:|---:|--:|---:|---:|---:|
| **0x00** | 7 | 12 | 17 | 22 | 7 | 12 | 17 | 22 |
| **0x10** | 5 |  9 | 14 | 20 | 5 |  9 | 14 | 20 |
| **0x20** | 4 | 11 | 16 | 23 | 4 | 11 | 16 | 23 |
| **0x30** | 6 | 10 | 15 | 21 | 6 | 10 | 15 | 21 |

| i | 8 | 9 | A | B | C | D | E | F |
|:----:|--:|---:|---:|---:|--:|---:|---:|---:|
| **0x00** | 7 | 12 | 17 | 22 | 7 | 12 | 17 | 22 |
| **0x10** | 5 |  9 | 14 | 20 | 5 |  9 | 14 | 20 |
| **0x20** | 4 | 11 | 16 | 23 | 4 | 11 | 16 | 23 |
| **0x30** | 6 | 10 | 15 | 21 | 6 | 10 | 15 | 21 |


横の 4 以降は、0〜3の繰り返しなので

| i | 0 | 1 | 2 | 3 |
|:----:|--:|---:|---:|---:|
| **0x00** | 7 | 12 | 17 | 22 |
| **0x10** | 5 |  9 | 14 | 20 |
| **0x20** | 4 | 11 | 16 | 23 |
| **0x30** | 6 | 10 | 15 | 21 |

に注目します。これを

| i | 0 | 1 | 2 | 3 |
|:----:|:------------:|:------------:|:------------:|:------------:|
| **0x00** | 4+(5\*0)+0+3 | 4+(5\*1)+0+3 | 4+(5\*2)+0+3 | 4+(5\*3)+1+2 |
| **0x10** | 4+(5\*0)+0+1 | 4+(5\*1)+0+0 | 4+(5\*2)+0+0 | 4+(5\*3)+1+0 |
| **0x20** | 4+(5\*0)+0+0 | 4+(5\*1)+0+2 | 4+(5\*2)+0+2 | 4+(5\*3)+1+3 |
| **0x30** | 4+(5\*0)+0+2 | 4+(5\*1)+0+1 | 4+(5\*2)+0+1 | 4+(5\*3)+1+1 |

に分解すると、最後の加算値は

| i | 0 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|:-:|
| **0x00** | 3 | 3 | 3 | 2 |
| **0x10** | 1 | 0 | 0 | 0 |
| **0x20** | 0 | 2 | 2 | 3 |
| **0x30** | 2 | 1 | 1 | 1 |

となるので、2ビット値にして逆順にすると

| i | 3 | 2 | 1 | 0 | 2進数 | 16進数 |
|:----:|:-:|:-:|:-:|:-:|:---------------------------:|:-:|
| **0x30** | 1 | 1 | 1 | 2 | <code>01\_01\_01\_10</code> | 56 |
| **0x20** | 3 | 2 | 2 | 0 | <code>11\_10\_10\_00</code> | e8 |
| **0x10** | 0 | 0 | 0 | 1 | <code>00\_00\_00\_01</code> | 01 |
| **0x00** | 2 | 3 | 3 | 3 | <code>10\_11\_11\_11</code> | bf |

2ビット×16 の参照テーブル（0x56e801bf）が出来上がります。


# プログラム

<details><summary>C++版</summary><div>

```c++
//
// ヘッダ用
//

#include <cstddef>
#include <cstdint>

/*
 * MD5ByteSum
 */

class MD5ByteSum
{
public:
    typedef uint32_t State[4];
    typedef uint32_t Block[16];
    typedef uint8_t Digest[16];
    typedef char HexDigest[33];

protected:
    static const uint8_t padding[64];

    State state;
    uint32_t bytes;
    Block input;
    bool active;

public:
    MD5ByteSum();
    MD5ByteSum(const void *message, size_t size);

    void digest(Digest &out);
    void hexdigest(HexDigest &out);

    void initialize();
    void update(const void *message, size_t size);
    void finalize();

protected:
    void update_state();
};

/*
 * MD5ByteSum - inline
 */

inline MD5ByteSum::MD5ByteSum()
{
    initialize();
}

//
// コンパイル用
//

/*
 * MD5ByteSum::State - update 16-Word block
 */

inline static uint32_t ROL(uint32_t x, int s)
{
    return ((x << s) | (x >> (32 - s)));
}

inline static uint32_t get_block_index(uint32_t index)
{
    /*
     * [y|y|x|x|x|x]
     *  (index * 1 + 0) & 15
     *  (index * 5 + 1) & 15
     *  (index * 3 + 5) & 15
     *  (index * 7 + 0) & 15
     */
    uint32_t x = index & 0x0f;
    uint32_t y = index & 0x30;
    uint32_t y1 = index & 0x10;
    uint32_t y2 = index & 0x20;
    uint32_t xmul = (y1 >> 2) | (y2 >> 4) | 1;
    uint32_t offs = (0x0510 >> (y >> 2)) & 7;
    return (x * xmul + offs) & 15;
}

inline static int get_rotate_bits(uint32_t index)
{
    /*
     * [y|y|.|.|x|x]
     *  7 12 17 22 : 3 8 13 18 : 3 3 3 3 : 3 3 3 2
     *  5  9 14 20 : 1 5 10 16 : 1 0 0 1 : 1 0 0 0
     *  4 11 16 23 : 0 7 12 19 : 0 2 2 4 : 0 2 2 3
     *  6 10 15 21 : 2 6 11 17 : 2 1 1 2 : 2 1 1 1
     *              -4          -(x*5)    -(x==3)
     *
     *  11 11 11 10 : 10_11_11_11 = bf
     *  01 00 00 00 : 00_00_00_01 = 01
     *  00 10 10 11 : 11_10_10_00 = e8
     *  10 01 01 01 : 01_01_01_10 = 56
     */
    uint32_t x = index & 0x03;
    uint32_t y = index & 0x30;
    uint32_t p = x | (y >> 2);
    uint32_t x0 = (0x56e801bf >> (p << 1)) & 3;
    uint32_t x3 = (x + 1) >> 2; // (x == 3) ? 1 : 0;
    uint32_t x5 = x * 5;
    return x0 + x3 + x5 + 4;
}

inline static uint32_t get_state_index(uint32_t index, uint32_t element)
{
    /*
     *  0 1 2 3
     *  3 0 1 2
     *  2 3 0 1
     *  1 2 3 0
     */
    return ((index * 3) + element) & 3;
}

inline static uint32_t md5bs_state_func(uint32_t index, uint32_t x, uint32_t y, uint32_t z)
{
    switch ((index >> 4) & 3)
    {
    case 0: return (y & x) | (z & ~x);
    case 1: return (x & z) | (y & ~z);
    case 2: return x ^ y ^ z;
    case 3: return y ^ (x | ~z);
    }
    return 0;
}

inline static void md5bs_state_update(uint32_t index, uint32_t *S, const MD5ByteSum::Block &X, uint32_t T)
{
    uint32_t a = get_state_index(index, 0);
    uint32_t b = get_state_index(index, 1);
    uint32_t c = get_state_index(index, 2);
    uint32_t d = get_state_index(index, 3);
    uint32_t x = get_block_index(index);
    uint32_t r = get_rotate_bits(index);

    S[a] = S[b] + ROL(X[x] + T + S[a] + md5bs_state_func(index, S[b], S[c], S[d]), r);
}

inline static void md5bs_state_update(uint32_t index, uint32_t *S,
                                      const MD5ByteSum::Block &X,
                                      uint32_t T1, uint32_t T2,
                                      uint32_t T3, uint32_t T4)
{
    md5bs_state_update(index + 0, S, X, T1);
    md5bs_state_update(index + 1, S, X, T2);
    md5bs_state_update(index + 2, S, X, T3);
    md5bs_state_update(index + 3, S, X, T4);
}

void MD5ByteSum::update_state()
{
    State p;

    p[0] = state[0];
    p[1] = state[1];
    p[2] = state[2];
    p[3] = state[3];

    // Round 1.
    md5bs_state_update( 0 * 4, state, input, 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee);
    md5bs_state_update( 1 * 4, state, input, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501);
    md5bs_state_update( 2 * 4, state, input, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be);
    md5bs_state_update( 3 * 4, state, input, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821);

    // Round 2.
    md5bs_state_update( 4 * 4, state, input, 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa);
    md5bs_state_update( 5 * 4, state, input, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8);
    md5bs_state_update( 6 * 4, state, input, 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed);
    md5bs_state_update( 7 * 4, state, input, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a);

    // Round 3.
    md5bs_state_update( 8 * 4, state, input, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c);
    md5bs_state_update( 9 * 4, state, input, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70);
    md5bs_state_update(10 * 4, state, input, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05);
    md5bs_state_update(11 * 4, state, input, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665);

    // Round 4.
    md5bs_state_update(12 * 4, state, input, 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039);
    md5bs_state_update(13 * 4, state, input, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1);
    md5bs_state_update(14 * 4, state, input, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1);
    md5bs_state_update(15 * 4, state, input, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391);

    state[0] += p[0];
    state[1] += p[1];
    state[2] += p[2];
    state[3] += p[3];
}

/*
 * MD5ByteSum
 */

const uint8_t MD5ByteSum::padding[64] = { 0x80 };

MD5ByteSum::MD5ByteSum(const void *message, size_t size)
{
    initialize();
    update(message, size);
    // finalize();
}

void MD5ByteSum::initialize()
{
    state[0] = 0x67452301;
    state[1] = 0xefcdab89;
    state[2] = 0x98badcfe;
    state[3] = 0x10325476;
    bytes = 0;
    for (int i = 0; i < 16; i++)
        input[i] = 0;
    active = true;
}

void MD5ByteSum::finalize()
{
    if (!active)
        return;

    uint32_t l = bytes;
    uint32_t i = l & 0x3f;
    uint32_t n = ((i >= 56) ? 64 : 0) + 56 - i;

    update(padding, n);

    input[14] = l << 3;
    input[15] = l >> 29;
    update_state();

    active = false;
}

void MD5ByteSum::update(const void *message, size_t size)
{
    if (!active)
        initialize();

    const uint8_t *d = reinterpret_cast<const uint8_t *>(message);
    unsigned b = (bytes & 3) << 3;
    unsigned i = (bytes >> 2) & 0x0f;

    bytes += size;
    while (size-- > 0)
    {
        input[i] |= (*d++) << b;

        b = (b + 8) & 0x1f;
        if (b == 0)
        {
            i = (i + 1) & 0x0f;
            if (i == 0)
                update_state();
            input[i] = 0;
        }
    }
}

void MD5ByteSum::digest(Digest &out)
{
    finalize();

    for (int p = 0; p < 4; p++)
    {
        uint32_t s = state[p];

        for (int q = 0; q < 4; q++, s >>= 8)
            out[p * 4 + q] = uint8_t(s);
    }
}

void MD5ByteSum::hexdigest(HexDigest &out)
{
    finalize();

    for (int p = 0; p < 4; p++)
    {
        uint32_t s = state[p];

        for (unsigned q = 0; q < 4; q++, s >>= 8)
        {
            char h = (s >> 4) & 0x0f;
            char l = (s >> 0) & 0x0f;
            out[p * 8 + q * 2 + 0] = h + ((h < 10) ? '0' : ('a' - 10));
            out[p * 8 + q * 2 + 1] = l + ((l < 10) ? '0' : ('a' - 10));
        }
    }
    out[32] = 0;
}

//
// テスト用
//

#include <cstdio>
#include <cstring>

int main(int argc, char **argv)
{
    const char *program = argv[0];

    if (argc != 2)
    {
        printf("usage: %s message\n", program);
        return 1;
    }

    const char *message = argv[1];

    MD5ByteSum md5(message, strlen(message));
    MD5ByteSum::HexDigest res;
    md5.hexdigest(res);
    printf("MD5 (\"%s\") = %s\n", message, res);
    return 0;
}
```

</div></details>

頭の体操として python/swift でも作ってみた。python では hashlib を、 swift では CommonCrypto を使った方がよいです。

<details><summary>Python版</summary><div>

```python:
#!/usr/bin/env python3

import math


def md5s(msg, encoding='utf-8'):
    if type(msg) in (bytes, bytearray):
        inp = bytearray(msg)
    elif type(msg) == str:
        inp = bytearray(msg, encoding)
    else:
        raise Exception('unknown type: %s' % type(msg))

    U32M = 0xffffffff
    def rotate(x, r): return (((U32M >> r) & x) << r) | ((U32M & x) >> (32 - r))
    def round1(a, b, c, d, x, t, r): return U32M & (b + rotate(x + t + a + ((b & c) | (d & (U32M - b))), r))
    def round2(a, b, c, d, x, t, r): return U32M & (b + rotate(x + t + a + ((b & d) | (c & (U32M - d))), r))
    def round3(a, b, c, d, x, t, r): return U32M & (b + rotate(x + t + a + (b ^ c ^ d), r))
    def round4(a, b, c, d, x, t, r): return U32M & (b + rotate(x + t + a + (c ^ (b | (U32M - d))), r))

    dsz = len(inp)
    bsz = dsz << 3
    pos = dsz & 0x3f
    psz = ((pos + 8) & 0x40) + 56 - pos
    inp += bytearray([0x80] + [0] * (psz - 1))
    inp += bytearray([(bsz >> b) & 0xff for b in range(0, 64, 8)])
    inp = tuple([inp[i] + (inp[i + 1] << 8) + (inp[i + 2] << 16) + (inp[i + 3] << 24) for i in range(0, len(inp), 4)])

    Sn = ((0, 1, 2, 3), (3, 0, 1, 2), (2, 3, 0, 1), (1, 2, 3, 0)) * 16
    Fn = (round1, round2, round3, round4)
    X1 = (0, 1, 2, 3) * 4 + (1, 6, 11, 0) * 4 + (13, 0, 3, 6) * 4 + (0, 7, 14, 5) * 4
    X4 = (0, 4, 8, 12) * 2 + (8, 4, 0, 12) + (0, 12, 8, 4)
    T = tuple([int(abs(math.sin(i + 1)) * 0x100000000) for i in range(64)])
    Rn = (7, 12, 17, 22) * 4 + (5, 9, 14, 20) * 4 + (4, 11, 16, 23) * 4 + (6, 10, 15, 21) * 4
    Z = tuple([(Sn[i], Fn[i >> 4], (X1[i] + X4[i >> 2]) & 0x0f, T[i], Rn[i]) for i in range(64)])

    S = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
    for X in range(0, len(inp), 16):
        ss = S * 1
        for ((a, b, c, d), f, x, t, r) in Z:
            S[a] = f(S[a], S[b], S[c], S[d], inp[X + x], t, r)
        for i in range(4):
            S[i] = U32M & (S[i] + ss[i])

    return bytes([(s >> b) & 0xff for s in S for b in range(0, 32, 8)])


# Test

sample = (
    ('', 'd41d8cd98f00b204e9800998ecf8427e'),
    ('a', '0cc175b9c0f1b6a831c399e269772661'),
    ('abc', '900150983cd24fb0d6963f7d28e17f72'),
    ('message digest', 'f96b697d7cb7938d525a2f31aaf161d0'),
    ('abcdefghijklmnopqrstuvwxyz', 'c3fcd3d76192e4007dfb496cca67e13b'),
    ('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789', 'd174ab98d277d9f5a5611c2c9f419d9f'),
    ('12345678901234567890123456789012345678901234567890123456789012345678901234567890', '57edf4a22be3c955ac49da2e2107b67a'),
)

for (message, digest) in sample:
    res = md5s(message)
    if res.hex() != digest:
        raise Exception('message "%s":\n   %s != %s' % (message, digest, res.hex()))
    print('MD5 ("%s") = %s' % (message, res.hex()))
```

</div></details>

<details><summary>Python（縦短横長）版</summary><div>

Sn, X1, X4, Rn は Z 中の計算で求めるようにするなどして、改行を減らして短くなったように見えるもの。

```python:
#!/usr/bin/env python3

import math


def md5s(msg, encoding='utf-8'):
    if type(msg) in (bytes, bytearray):
        inp = bytearray(msg)
    elif type(msg) == str:
        inp = bytearray(msg, encoding)
    else:
        raise Exception('unknown type: %s' % type(msg))

    psz = (((len(inp) & 0x3f) + 8) & 0x40) + 56 - (len(inp) & 0x3f)
    inp += bytearray([0x80] + [0] * (psz - 1)) + bytearray([((len(inp) << 3) >> b) & 0xff for b in range(0, 64, 8)])
    inp = tuple([inp[i] + (inp[i + 1] << 8) + (inp[i + 2] << 16) + (inp[i + 3] << 24) for i in range(0, len(inp), 4)])

    Z = tuple([(tuple([(i * 3 + j) & 3 for j in range(4)]), (lambda x, y, z: (x & y) | (z & (0xffffffff - x)), lambda x, y, z: (x & z) | (y & (0xffffffff - z)), lambda x, y, z: x ^ y ^ z, lambda x, y, z: y ^ (x | (0xffffffff - z)))[i >> 4], ((((i >> 2) & 4) | ((i >> 4) & 2) | 1) * (i & 15) + ((0x0510 >> ((i >> 2) & 12)) & 15)) & 15, int(abs(math.sin(i + 1)) * 0x100000000), ((0x56e801bf >> ((((i >> 2) & 12) | (i & 3)) << 1)) & 3) + (((i & 3) + 1) >> 2) + ((i & 3) * 5) + 4) for i in range(64)])

    S = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
    for X in range(0, len(inp), 16):
        ss = S * 1
        for ((a, b, c, d), f, x, t, r) in Z:
            S[a] = 0xffffffff & (S[b] + (lambda x, r: (((0xffffffff >> r) & x) << r) | ((0xffffffff & x) >> (32 - r)))(inp[X + x] + t + S[a] + f(S[b], S[c], S[d]), r))
        for i in range(4):
            S[i] = 0xffffffff & (S[i] + ss[i])
    return bytes([(s >> b) & 0xff for s in S for b in range(0, 32, 8)])


# Test

sample = (
    ('', 'd41d8cd98f00b204e9800998ecf8427e'),
    ('a', '0cc175b9c0f1b6a831c399e269772661'),
    ('abc', '900150983cd24fb0d6963f7d28e17f72'),
    ('message digest', 'f96b697d7cb7938d525a2f31aaf161d0'),
    ('abcdefghijklmnopqrstuvwxyz', 'c3fcd3d76192e4007dfb496cca67e13b'),
    ('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789', 'd174ab98d277d9f5a5611c2c9f419d9f'),
    ('12345678901234567890123456789012345678901234567890123456789012345678901234567890', '57edf4a22be3c955ac49da2e2107b67a'),
)

for (message, digest) in sample:
    res = md5s(message)
    if res.hex() != digest:
        raise Exception('message "%s":\n   %s != %s' % (message, digest, res.hex()))
    print('MD5 ("%s") = %s' % (message, res.hex()))
```

</div></details>

<details><summary>Swift版</summary><div>

Xcode 12.5.1 での Console アプリとして作っています。

```swift:main.swift
import Foundation

// ############

infix operator <<<
func <<< (x: UInt32, s: Int) -> UInt32 {
    return (x &<< s) | (x >> (32 - s))
}

extension Data {
    func ToArrayU8() -> [UInt8] {
        return [UInt8](unsafeUninitializedCapacity: count)
        { buffer, initializedCount in
            copyBytes(to: buffer, from: 0..<count)
            initializedCount = count
        }
    }
}

class MD5ByteSum {
    static let Rmap: [[Int]] = [
        [ 7, 12, 17, 22 ],
        [ 5,  9, 14, 20 ],
        [ 4, 11, 16, 23 ],
        [ 6, 10, 15, 21 ],
    ]
    static let Smap: [[Int]] = [
        [ 0, 1, 2, 3 ],
        [ 3, 0, 1, 2 ],
        [ 2, 3, 0, 1 ],
        [ 1, 2, 3, 0 ],
    ]
    static let T: [UInt32] = [UInt32](unsafeUninitializedCapacity: 64)
    { buffer, initializedCount in
        for i in 0..<64 {
            let t = abs(sin(Double(i + 1))) * 4294967296
            buffer[i] = UInt32(UInt64(t) & 0xffffffff)
        }
        initializedCount = 64
    }
    static let state0: [UInt32] = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476]
    var state: [UInt32] = MD5ByteSum.state0
    var count: UInt32 = 0
    var input: [UInt32] = Array(repeating: 0, count: 16)
    var close = false
    init() {}
    init(_ message: [UInt8]) {
        update(message)
    }
    init(_ message: String) {
        update(Data(message.utf8).ToArrayU8())
    }
    func fini() {
        if !close {
            let bytes = count
            let i = Int(bytes & 0x3f)
            let n = ((i >= 56) ? 64 : 0) + 56 - i;
            update([0x80])
            if n > 1 {
                update(Array(repeating: 0, count: n - 1))
            }
            input[14] = bytes &<< 3
            input[15] = bytes >> 29
            update_state()
        }
        close = true
    }
    func clear() {
        state = MD5ByteSum.state0
        count = 0
        input[0] = 0
        close = false
    }
    func update(_ message: String) {
        update(Data(message.utf8).ToArrayU8())
    }
    func update(_ message: [UInt8]) {
        if close {
            clear()
        }
        var b = Int((count & 3) << 3)
        var i = Int((count >> 2) & 0x0f)
        count += UInt32(message.count)
        for d in message {
            input[i] |= UInt32(d) << b
            b = (b + 8) & 0x1f
            if b == 0 {
                i = (i + 1) & 0x0f
                if i == 0 {
                    update_state()
                }
                input[i] = 0
            }
        }
    }
    func update_state() {
        let p = state
        update_digest()
        for n in 0..<4 {
            state[n] &+= p[n]
        }
    }
    func update_digest() {
        var k: Int

        // Round 1.
        let R1 = MD5ByteSum.Rmap[0]
        for i in 0..<16 {
            let S = MD5ByteSum.Smap[i & 3]
            let a = S[0], A = state[a]
            let b = S[1], B = state[b]
            let c = S[2], C = state[c]
            let d = S[3], D = state[d]
            k = i
            state[a] = B &+ ((A &+ ((C & B) | (D & ~B)) &+ MD5ByteSum.T[i] &+ input[k]) <<< R1[i & 3])
        }

        // Round 2.
        k = 1
        let R2 = MD5ByteSum.Rmap[1]
        for i in 16..<32 {
            let S = MD5ByteSum.Smap[i & 3]
            let a = S[0], A = state[a]
            let b = S[1], B = state[b]
            let c = S[2], C = state[c]
            let d = S[3], D = state[d]
            state[a] = B &+ ((A &+ ((B & D) | (C & ~D)) &+ MD5ByteSum.T[i] &+ input[k]) <<< R2[i & 3])
            k = (k + 5) & 0x0f
        }

        // Round 3.
        k = 5
        let R3 = MD5ByteSum.Rmap[2]
        for i in 32..<48 {
            let S = MD5ByteSum.Smap[i & 3]
            let a = S[0], A = state[a]
            let b = S[1], B = state[b]
            let c = S[2], C = state[c]
            let d = S[3], D = state[d]
            state[a] = B &+ ((A &+ (B ^ C ^ D) &+ MD5ByteSum.T[i] &+ input[k]) <<< R3[i & 3])
            k = (k + 3) & 0x0f
        }

        // Round 4.
        k = 0
        let R4 = MD5ByteSum.Rmap[3]
        for i in 48..<64 {
            let S = MD5ByteSum.Smap[i & 3]
            let a = S[0], A = state[a]
            let b = S[1], B = state[b]
            let c = S[2], C = state[c]
            let d = S[3], D = state[d]
            state[a] = B &+ ((A &+ (C ^ (B | ~D)) &+ MD5ByteSum.T[i] &+ input[k]) <<< R4[i & 3])
            k = (k + 7) & 0x0f
        }
    }
    func digest() -> [UInt8] {
        fini()
        return [UInt8](unsafeUninitializedCapacity: 16)
        { buffer, initializedCount in
            for i in 0..<4 {
                for j in 0..<4 {
                    buffer[i * 4 + j] = UInt8((state[i] >> (j << 3)) & 0xff)
                }
            }
            initializedCount = 16
        }
    }
    func hexdigest() -> String {
        var s = ""
        for c in digest() {
            s += String(format: "%02x", c)
        }
        return s
    }
}

// ############

func test() {
    let sample: [[String]] = [
        [ "d41d8cd98f00b204e9800998ecf8427e", "" ],
        [ "0cc175b9c0f1b6a831c399e269772661", "a" ],
        [ "900150983cd24fb0d6963f7d28e17f72", "abc" ],
        [ "f96b697d7cb7938d525a2f31aaf161d0", "message digest" ],
        [ "c3fcd3d76192e4007dfb496cca67e13b", "abcdefghijklmnopqrstuvwxyz" ],
        [ "d174ab98d277d9f5a5611c2c9f419d9f", "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" ],
        [ "57edf4a22be3c955ac49da2e2107b67a", "12345678901234567890123456789012345678901234567890123456789012345678901234567890" ],
    ]
    for t in sample {
        let md5 = MD5ByteSum(t[1])
        let res = md5.hexdigest()
        if res != t[0] {
            print("Message: \"\(t[1])\"")
            print("  Error: \(t[0]) != \(res)")
            exit(1)
        }
        print("MD5 (\"\(t[1])\") = \(res)")
    }
}
test()
```

</div></details>