<?php 
declare(strict_types=1);
class Algorithm
{
    public function sha256(string $str): string
    {
        // 步驟一：將字符串轉化為二進制
         $this->step1_convert_str_to_bits($str);
 
        // 步驟二：在最后面追加一個1
         $this->step2_append_1();
 
        // 步驟三：在數據末尾添加0，確保二進制的個數是512的倍數，最后預留64位用于存儲原始長度信息
         $this->step3_extend_to_multiple_of_512();
 
        // 步驟四：把原始字符串位長度，填充到預留在最后的64位（8個字節(jié)的長整型）中
         $this->step4_append_origin_length();
 
        // 步驟五：每一個512位切分區(qū)塊，在區(qū)塊末尾填充0，使得每個區(qū)塊位數為2048位，需要增加48行（32位一行）
         $this->step5_split_blocks_and_append_48_lines();
 
        // 步驟六：針對每一個2048位區(qū)塊處理：以32位為一行，總共有64行，修改【16-63】行的數據
         $this->step6_modify_blocks_appended_48_lines();
 
        // 步驟七：壓縮數據，生成最終的哈希值
        return $this->step7_compress_to_final_hash();
    }
}

/** @var int 原始數據的二進制長度  */
private int $originLen = 0;

/** @var array 存儲二進制數組 */
private array $bits;

/** @var array 二進制區(qū)塊 */
private array $blocks;

/** @var array 質數平方根常量 */
private const H = [
    0x6a09e667, // 質數2的平方根取二進制小數部分前32位
    0xbb67ae85, // 質數3的平方根取二進制小數部分前32位
    0x3c6ef372, // 質數5的平方根取二進制小數部分前32位
    0xa54ff53a, // 質數7的平方根取二進制小數部分前32位
    0x510e527f, // 質數11的平方根取二進制小數部分前32位
    0x9b05688c, // 質數13的平方根取二進制小數部分前32位
    0x1f83d9ab, // 質數17的平方根取二進制小數部分前32位
    0x5be0cd19, // 質數19的平方根取二進制小數部分前32位
];

小數轉二進制
                            0.
0.4142135623730950488016887242097 x 2 => 0
0.8284271247461900976033774484194 x 2 => 1
0.6568542494923801952067548968388 x 2 => 1
0.3137084989847603904135097936776 x 2 => 0
0.6274169979695207808270195873552 x 2 => 1
0.2548339959390415616540391747104 x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 1
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
0.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ x 2 => 0
. . .

/** @var array 質數立方根常量 */
private const K = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
     0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
     0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
     0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
     0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
     0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
     0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
     0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
];

/**
 * 十進制整數轉化為二進制數組
 * @param int $num 十進制整數
 * @param int $fillTo 填充到多少位，不夠的用0來補齊
 */
 
public function int2bits(int $num, int $fillTo = 0): array
{
    $bits = str_split(decbin($num));
    array_walk($bits, function (&$val) {
        $val = intval($val);
    });
 
    for ($len = count($bits); $len < $fillTo; $len++) {
        array_unshift($bits, 0);
    }
    return $bits;
}

/**
 * 二進制數組向右移動
 * @param array $bits 二進制數組
 */
 
public function rightShift(array $bits, int $move): array
 
{
    $len = count($bits);
    $move = $move % $len;
    if ($move <= 0) return $bits;
    return array_merge(array_fill(0, $move, 0), array_slice($bits, 0, $len-$move));
}

/**
 * 二進制數組向右旋轉
 * @param array $bits 二進制數組
 */
 
public function rightRotate(array $bits, int $move): array
{
    $len = count($bits);
    $move = $move % $len;
    if ($move <= 0) return $bits;
    return array_merge(array_slice($bits, $len-$move, $move), array_slice($bits, 0, $len-$move));
}

/**
 * 二進制數組求非
 * @param array $bits 二進制數組
 */
 
public function not(array $bits): array
{
    for ($i = count($bits)-1; $i >= 0; $i--) {
        $bits[$i] = ($bits[$i] == 0) ? 1 : 0;
    }
    return $bits;
}

/**
 * 二進制數組求與
 * @param array $args 二進制數組
 */
 
public function and(array ...$args): array
{
 
    $argc = count($args);
    if ($argc == 0) return [];
    for ($i = 1; $i < $argc; $i++) {
        $j = count($args[0]) - 1;
        $k = count($args[$i]) - 1;
        while ($j >= 0 || $k >= 0) {
            $j < 0 and array_unshift($args[0], 0) and $j = 0; // 如果是$args[0]不夠長就頭插補齊
            ($args[$i][$k] ?? 0) == 0 and $args[0][$j] = 0;
            $j--;
            $k--;
        }
    }
    return $args[0];
}

/**
 * 二進制數組求異或
 * @param array $args 二進制數組
 */
 
public function xor(array ...$args): array
{
    $argc = count($args);
    if ($argc == 0) return [];
    for ($i = 1; $i < $argc; $i++) {
        $j = count($args[0]) - 1;
        $k = count($args[$i]) - 1;
        while ($j >= 0 || $k >= 0) {
            $j < 0 and array_unshift($args[0], 0) and $j = 0; // 如果是$args[0]不夠長就頭插補齊
            $args[0][$j] = intval($args[0][$j] != ($args[$i][$k] ?? 0));
            $j--;
            $k--;
        }
    }
    return $args[0];
}

/**
 * 二進制數組相加
 * @param array $args 二進制數組
 */
 
public function add(array ...$args): array
{
 
    $argc = count($args);
    if ($argc == 0) return [];
    for ($i = 1; $i < $argc; $i++) {
        $carry = 0;
        $j = count($args[0]) - 1;
        $k = count($args[$i]) - 1;
        while ($j >= 0 || $k >= 0) {
            $j < 0 and array_unshift($args[0], 0) and $j = 0; // 如果是$args[0]不夠長就頭插補齊
            $carry += $args[0][$j] + ($args[$i][$k] ?? 0);
            switch ($carry) {
                 case 1: $carry = 0; $args[0][$j] = 1; break;
                case 2: $carry = 1; $args[0][$j] = 0; break;
                case 3: $carry = 1; $args[0][$j] = 1; break;
            }
            $j--;
            $k--;
        }
        $carry == 1 and array_unshift($args[0], $carry); // 計算完后還有進位則加長存放
     }
    return array_slice($args[0], -32); // 計算結果只保留32位
}

/**
 * 打印二進制數組
 * @param array $bits 二進制數組
 */
 
public function printBits(array $bits): void
{
    $len = 0;
    foreach ($bits as $bit) {
        if ($len > 0) {
            if ($len % 512 == 0) echo PHP_EOL;
            if ($len % 64 == 0) {
                echo PHP_EOL;  
            } else {
                if ($len % 32 == 0) echo ' ';
                if ($len % 8 == 0) echo ' ';
            }
        }
        echo $bit;
        $len++;
    }
    echo PHP_EOL;
}

/**
 * 二進制數組轉化為十六進制
 * @param array $bits 二進制數組
 */
 
public function bits2hex(array $bits): string
{
    $str = '';
    for ($i = count($bits)-1; $i >= 0; $i -= 4) {
        $dec = $bits[$i] + ($bits[$i-1] ?? 0)*2 + ($bits[$i-2] ?? 0)*4 + ($bits[$i-3] ?? 0)*8;
        switch ($dec) {
            case 0:  $str = '0' . $str; break;
            case 1:  $str = '1' . $str; break;
            case 2:  $str = '2' . $str; break;
            case 3:  $str = '3' . $str; break;
            case 4:  $str = '4' . $str; break;
            case 5:  $str = '5' . $str; break;
            case 6:  $str = '6' . $str; break;
            case 7:  $str = '7' . $str; break;
            case 8:  $str = '8' . $str; break;
            case 9:  $str = '9' . $str; break;
            case 10: $str = 'a' . $str; break;
            case 11: $str = 'b' . $str; break;
            case 12: $str = 'c' . $str; break;
            case 13: $str = 'd' . $str; break;
            case 14: $str = 'e' . $str; break;
            case 15: $str = 'f' . $str; break;
        }
    }
    return $str;
}

/**
 * 步驟一：將字符串轉化為二進制
 * @param string $str 原始字符串
 */
 
public function step1_convert_str_to_bits(string $str): void
{
 
    $this->bits = [];
    $chars = str_split($str);
    foreach ($chars as $char) {
        $this->bits = array_merge($this->bits, $this->int2bits(ord($char), 8));
    }
    $this->originLen = count($this->bits);
}

/**
 * 步驟二：在最后面追加一個1
 */
 
public function step2_append_1(): void
{
    $this->bits[] = 1;
}

/**
 * 步驟三：在數據末尾添加0，確保二進制的個數是512的倍數，最后預留64位用于存儲原始長度信息
 */
 
public function step3_extend_to_multiple_of_512(): void
{
    $rem = (count($this->bits) + 64) % 512;
    if ($rem > 0) {
        while ($rem < 512) {
            $this->bits[] = 0;
            $rem++;
        }
    }
}

/**
 * 步驟四：把原始字符串位長度，填充到預留在最后的64位（8個字節(jié)的長整型）中
 */
 
public function step4_append_origin_length(): voi
 
{
    $this->bits = array_merge($this->bits, $this->int2bits($this->originLen, 64));
}

/**
 * 步驟五：每一個512位切分區(qū)塊，在區(qū)塊末尾填充0，使得每個區(qū)塊位數為2048位，經計算
 * 每個區(qū)塊還需要添加48x32個0
 */
 
public function step5_split_blocks_and_append_48_lines(): void
{
    $this->blocks = [];
    $append = $this->int2bits(0, 48 * 32);
    $len = count($this->bits);
    for ($i = 0; $i < $len; $i += 512) {
        $this->blocks[] = array_merge(array_slice($this->bits, $i, 512), $append);
    }
}

For i from w[16…63]:
????s0 = (w[i-15] rightrotate 7) xor (w[i-15] rightrotate 18) xor (w[i-15] rightshift 3)
????s1 = (w[i-2] rightrotate 17) xor (w[i- 2] rightrotate 19) xor (w[i- 2] rightshift 10)
 ????w[i] = w[i-16] + s0 + w[i-7] + s1

i = 16
(w[1] rightrotate 7) = 01101111001000000111011101101111 -> 11011110110111100100000011101110
(w[1] rightrotate 18) = 01101111001000000111011101101111 -> 00011101110110111101101111001000
(w[1] rightshift 3) = 01101111001000000111011101101111 -> 00001101111001000000111011101101
s0 = (w[1] rightrotate 7) xor (w[1] rightrotate 18) xor (w[1] rightshift 3)
?= 11001110111000011001010111001011
(w[14] rightrotate 17) = 00000000000000000000000000000000 -> 00000000000000000000000000000000
(w[14] rightrotate 19) = 00000000000000000000000000000000 -> 00000000000000000000000000000000
(w[14] rightshift 10) = 00000000000000000000000000000000 -> 00000000000000000000000000000000
s1 = (w[14] rightrotate 17) xor (w[14] rightrotate 19) xor (w[14] rightshift 10)
= 00000000000000000000000000000000
w[i] = w[0] + s0 + w[9] + s1
= 00110111010001110000001000110111（相加得到的值如果超過 32 位，則抹去高位）
/**
 * 步驟六：針對每一個2048位區(qū)塊處理：以32位為一行，總共有64行，修改【16-63】行的數據，
 * 這【16-63】行就是上一步新增的48x32個0
 */
 
public function step6_modify_blocks_appended_48_lines(): void
{
    foreach ($this->blocks as &$block) {
        for ($i = 16; $i < 64; $i++) {
            $w0 = array_slice($block, ($i-16)*32, 32);
            $w1 = array_slice($block, ($i-15)*32, 32);
            $w9 = array_slice($block, ($i-7)*32, 32);
            $w14 = array_slice($block, ($i-2)*32, 32);
            $s0 = $this->xor(   
                $this->rightRotate($w1, 7),
                $this->rightRotate($w1, 18),
                $this->rightShift($w1, 3)
            );
 
            $s1 = $this->xor(
                $this->rightRotate($w14, 17),
                $this->rightRotate($w14, 19),
                $this->rightShift($w14, 10)
            );
 
            $wi = $this->add($w0, $s0, $w9, $s1);
            // 如果$wi的長度超過了32位，則只取32位，舍棄高位
            $k = count($wi) - 1;
            for ($j = $i * 32 + 31; $j >= $i * 32; $j--) {
                $block[$j] = $wi[$k] ?? 0;
                $k--;
            }
        }
    }
}

For i from 0 to 63
????s1 = (e rightrotate 6) xor (e rightrotate 11) xor (e rightrotate 25)
????ch = (e and f) xor ((not e) and g)
????temp1 = h + s1 + ch + k[i] + w[i]
????s0 = (a rightrotate 2) xor (a rightrotate 13) xor (a rightrotate 22)
????maj = (a and b) xor (a and c) xor (b and c)
????temp2 := s0 + maj
????h = g
????g = f
????f = e
????e = d + temp1
????d = c
????c = b
????b = a
????a = temp1 + temp2

/**
 * 步驟七：壓縮數據
 */
 
public function step7_compress_to_final_hash(): string
{
 
    $a = $h0 = $this->int2bits(static::H[0], 32);
    $b = $h1 = $this->int2bits(static::H[1], 32);
    $c = $h2 = $this->int2bits(static::H[2], 32);
    $d = $h3 = $this->int2bits(static::H[3], 32);
    $e = $h4 = $this->int2bits(static::H[4], 32);
    $f = $h5 = $this->int2bits(static::H[5], 32);
    $g = $h6 = $this->int2bits(static::H[6], 32);
    $h = $h7 = $this->int2bits(static::H[7], 32);
    foreach ($this->blocks as $block) {
        for ($i = 0; $i < 64; $i++) {
            $s1 = $this->xor(
                $this->rightRotate($e, 6),
                $this->rightRotate($e, 11),
                $this->rightRotate($e, 25)
            );
 
            $ch = $this->xor(
                $this->and($e, $f),
                $this->and($this->not($e), $g)
            );
 
            $ki = $this->int2bits(static::K[$i], 32);
            $wi = array_slice($block, $i*32, 32);
            $temp1 = $this->add($h, $s1, $ch, $ki, $wi);
            $s0 = $this->xor(
                $this->rightRotate($a, 2),
                $this->rightRotate($a, 13),
                $this->rightRotate($a, 22),
            );
 
            $maj = $this->xor(
                $this->and($a, $b),
                $this->and($a, $c),
                $this->and($b, $c)
            );
 
            $temp2 = $this->add($s0, $maj);
            $h = $g;
            $g = $f;
            $f = $e;
            $e = $this->add($d, $temp1);
            $d = $c;
            $c = $b;
            $b = $a;
            $a = $this->add($temp1, $temp2);
        }
    }
 
    $h0 = $this->add($h0, $a);
    $h1 = $this->add($h1, $b);
    $h2 = $this->add($h2, $c);
    $h3 = $this->add($h3, $d);
    $h4 = $this->add($h4, $e);
    $h5 = $this->add($h5, $f);
    $h6 = $this->add($h6, $g);
    $h7 = $this->add($h7, $h);
    return $this->bits2hex(array_merge($h0, $h1, $h2, $h3, $h4, $h5, $h6, $h7));
}