[C] Implement SHA-1

最近因為工作需要把一串字串經過處理後變成另一個長度最多 48-byte 的唯一的字串，能做到這類事情理所當然地就會往 MD5、SHA-1 這類 hash function 去找，而且因為不是要用作加密金鑰，對於安全性的要求並不高，所以後來就選了 SHA-1 當作目標。

實際看了下演算法，其實超簡單的...雖然會有一些細節要特別注意，但整體上的實作相當容易。以下就一一說明要注意的細節，C code 就放在最後面供參囉。

首先完整演算法可以直接參考 wikipedia 上的 pseudo code。不過最值得注意的一個重點在於 endian 的考量：SHA-1 基本上就是把 input 看成一串 bit stream，並且後面所有基於 32-bit WORD 為單位的 bitwise 及 arithmetic operations 都是基於 big endian 來做設計的，所以在現在許多平台都是走 little endian 的前提下，在運算上要特別注意這點，不然就會發現 hash 後的結果跟其他人都不同。這點在 SHA-1 基於 convention 的常數最為明顯 (下面列表的 H0 ~ H4 及 K1 ~ K4 這 9 個常數)

#define H0 0x67452301
#define H1 0xEFCDAB89
#define H2 0x98BADCFE
#define H3 0x10325476
#define H4 0xC3D2E1F0

#define K1 0x5A827999 // sqrt(2)
#define K2 0x6ED9EBA1 // sqrt(3)
#define K3 0x8F1BBCDC // sqrt(5)
#define K4 0xCA62C1D6 // sqrt(10)

同樣是 endian 衍伸的問題可以在 pseudo code 中的這一行發現：

append length of message (before pre-processing), in bits, as 64-bit big-endian integer

所以這一行對應的 code 就會發現抓那 64-bit 的 integer 的每個 byte 的時，放的順序會跟拿的順序相反 (line 49 ~ 56)

static inline void appendInputSize(char* chunk, int chunk_size, uint64_t input_size)
{
    char* ptr = (char*)(&input_size);
    for (int i = 0, idx = chunk_size; i < sizeof(input_size); ++i) {
        chunk[--idx] = *ptr;
        ++ptr;
    }
}

不過這邊可以再多注意一個細節：原始資料長度是用 bit 而不是 byte 計算，一開始沒注意到這點，還一直再想說到底哪邊寫錯為什麼就是不同...

preprocess 後、進入 main loop 前也有一段 code 是為了在轉成 32-bit unsigned integer 前確保運算結果符合 little endian 的方式所以做的轉換 (line 142 ~ 146)

// 32-bit big endian to 32-bit little endian
for (int i = 0; i < chunk_size; i += 4) {
    swap(chunk+i, chunk+i+3);
    swap(chunk+i+1, chunk+i+2);
}

當然，最後輸出時也要再轉成正確的順序 (line 117 ~ 127)

static inline void toHex(uint32_t value, char* out)
{
    const char* HEX_VAL = "0123456789ABCDEF";
    unsigned char* ptr = (unsigned char*)(&value);
    int idx = sizeof(value) << 1;
    for (int i = 0; i < sizeof(value); ++i) {
        out[--idx] = HEX_VAL[(*ptr) & 0x0F];
        out[--idx] = HEX_VAL[(*ptr) >> 4];
        ++ptr;
    }
}

大致上只要注意這些點、照著做就能寫出來了，演算法流程這邊就不多說了，請參考下面完整的 source code