HsuChiChen/huffman.v

## huffman.v
//############################################################################
//   2018 IC Contest graduate group preliminary round
//   Topic         : Huffman Coding
//   Author        : HsuChiChen (chenneil90121@gmail.com)
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//   Date          : 2024.02.24
//   Version       : v1.0
//   File Name     : huffman.v
//   Module Name   : huffman
//############################################################################
// Huffman coding is a method of lossless data compression.
// It assigns variable-length codes to input characters, the length of the code depends on the frequency of the character.
// The most frequent character gets the smallest code and the least frequent character gets the largest code.
// The codes are prefix-free, which means that no code is a prefix of another code.
// This is useful for decoding, as it means that the code can be read one bit at a time and the result will be unambiguous.

// My algorithm is as follows:
// 1. count the number of 6 character from gray image in 100 cycles
// 2. sort the 6 character and 6 weight in 5 cycles. Simulatuously, calculate the Huffman code and code length
// Do not need to establish Huffman tree, just use the pointer to top node for node 0 ~ 5
// 3. output the number of 6 characters, Huffman code, and mask for each character's Huffman code in 1 cycle

// In TSMC 0.13um technology, latency is 5 cycles
// when cycle time is 5ns, total cell area 41584 um^2
// when cycle time is 6ns, total cell area 35080 um^2
// when cycle time is 10ns, total cell area 26710 um^2

module huffman(
    // Input Ports
    clk, reset, gray_valid, gray_data, CNT_valid,
    // Output Ports
    CNT1, CNT2, CNT3, CNT4, CNT5, CNT6, // number of  6 characters (symbol)
    code_valid, HC1, HC2, HC3, HC4, HC5, HC6, // each character's Huffman code
    M1, M2, M3, M4, M5, M6); // mask for each character's Huffman code

//==============================================//
//          Input & Output Declaration          //
//==============================================//
// Input Ports
input clk;
input reset;
input gray_valid;
input [7:0] gray_data;

// Output Ports
output reg CNT_valid;
output reg [7:0] CNT1, CNT2, CNT3, CNT4, CNT5, CNT6;
output reg code_valid;
output reg [7:0] HC1, HC2, HC3, HC4, HC5, HC6;
output reg [7:0] M1, M2, M3, M4, M5, M6;

//==============================================//
//             Parameter and Integer            //
//==============================================//
parameter   IDLE       = 0,
            READ       = 1,
            CACL       = 2,
            OUT_CODE   = 3;

integer i;
//==============================================//
//                 reg declaration              //
//==============================================//
// state machine
reg [1:0] current_state;

// state counter
reg [3:0] counter;

// pointer to top node
reg [3:0] head[0:5];

// 8-bit huffman code
reg [7:0] code[0:5];

// 4-bit code length
reg [3:0] code_length[0:5];

// input character
reg [4:0] char[0:5];

// image counter
reg [7:0] image_counter[0:5];

// input weight
reg [7:0] w[0:5];

//==============================================//
//       psedo-reg wire declaration             //
//==============================================//
// state machine
reg [1:0] next_state;

// sort network output
wire [4:0] out_char[0:5];
wire [7:0] out_w[0:5];

// sum of two weight
wire [7:0] out_w_sum;

//==============================================//
//             Current State Block              //
//==============================================//
always @(posedge clk or posedge reset) begin
    if(reset) current_state <= IDLE;
    else current_state <= next_state;
end

//==============================================//
//              Next State Block                //
//==============================================//
always @(*) begin
    case (current_state)
        // wait for read gray image
        IDLE: begin
            if (gray_valid) next_state = READ;
            else next_state = IDLE;
        end

        // read gray image with 100 cycles
        READ: begin
            if (gray_valid) next_state = READ;
            else next_state = CACL;
        end

        // 5 cycles calculate 6 weight
        CACL: begin
            if (counter == 4) next_state = OUT_CODE;
            else next_state = CACL;
        end

        // output Huffman code in one cycle
        OUT_CODE : begin
            next_state = IDLE;
        end
        default: next_state = IDLE; // illegal state
    endcase
end

//==============================================//
//    Counter for 5 cycles in CACL state        //
//==============================================//
always @(posedge clk or posedge reset) begin
    if(reset) begin
        counter <= 0;
    end else if (current_state == CACL) begin
        counter <= counter + 1;
    end else begin
        counter <= 0;
    end
end

//==================================================//
//  Pointer to top node, Huffman code, code length  //
//==================================================//
always @(posedge clk) begin
    if(current_state == READ) begin
        // initialize top node as node 0 ~ 5 itself
        for(i = 0; i < 6; i = i + 1) begin
            head[i] <= i;
        end

        // initialize Huffman code as 0
        for(i = 0; i < 6; i = i + 1) begin
            code[i] <= 0;
        end

        // initialize code length as 0
        for(i = 0; i < 6; i = i + 1) begin
            code_length[i] <= 0;
        end

    // The node with the 2nd smallest / 1st smallest weight will compare with node 0 ~ 5
    // If match the node, those node will update its pointer to top pointer
    // simultaneously, the Huffman code will add 0 / 1 in the front
    end else if(current_state == CACL) begin
        for(i = 0; i < 6; i = i + 1) begin
            // 2nd smallest be left child of top node, Huffman code add 0
            if(head[i] == out_char[4]) begin
                head[i] <= counter + 6; // update pointer to top pointer
                // code[i] <= (code[i] << 1) + 0; // Huffman code = 0
                code_length[i] <= code_length[i] + 1; // Huffman code length + 1

            // 1st smallest be right child of top node, Huffman code add 1
            end else if(head[i] == out_char[5]) begin
                head[i] <= counter + 6; // update pointer to top pointer
                code[i] <= code[i] + (1 << code_length[i]); // Huffman code = 1
                code_length[i] <= code_length[i] + 1; // Huffman code length + 1
            end
        end
    end
end

//==============================================//
//                sorting module                //
//==============================================//
sort_network s0(
    // Input character
    .char0(char[0]),
    .char1(char[1]),
    .char2(char[2]),
    .char3(char[3]),
    .char4(char[4]),
    .char5(char[5]),
    // Input weight
    .w0(w[0]),
    .w1(w[1]),
    .w2(w[2]),
    .w3(w[3]),
    .w4(w[4]),
    .w5(w[5]),
    // Output character
    .out_char0(out_char[0]),
    .out_char1(out_char[1]),
    .out_char2(out_char[2]),
    .out_char3(out_char[3]),
    .out_char4(out_char[4]),
    .out_char5(out_char[5]),
    // Output weight
    .out_w0(out_w[0]),
    .out_w1(out_w[1]),
    .out_w2(out_w[2]),
    .out_w3(out_w[3]),
    .out_w4(out_w[4]),
    .out_w5(out_w[5])
);

// sum of two weight
assign out_w_sum = out_w[4] + out_w[5];

//==============================================//
//           input character & weight           //
//==============================================//
// input character
always @(posedge clk) begin
    // initialize character
    if(current_state == READ) begin
        char[0] <= 0;
        char[1] <= 1;
        char[2] <= 2;
        char[3] <= 3;
        char[4] <= 4;
        char[5] <= 5;
    // 5 cycles sort 6 character
    end else if(current_state == CACL) begin
        char[0] <= out_char[0];
        char[1] <= out_char[1];
        char[2] <= out_char[2];
        char[3] <= out_char[3];
        char[4] <= 15;          // unused node
        char[5] <= counter + 6; // add new node named 6, 7, 8, 9, 10 (counter from 0 to 4)
    end
end

// input weight
always @(posedge clk) begin
    if(reset) begin
        for (i = 0; i < 6; i = i + 1) begin
            w[i] <= 0;
        end
    // count the frequency of each character from gray image with 100 cycles
    end else if (gray_valid) begin
        w[gray_data - 1] <= w[gray_data - 1] + 1;
    // 5 cycles sort 6 weight
    end else if(current_state == CACL) begin
        w[0] <= out_w[0];
        w[1] <= out_w[1];
        w[2] <= out_w[2];
        w[3] <= out_w[3];
        w[4] <= 255;         // unused weight
        w[5] <= out_w_sum;   // add new weight (sum of 2 smallest weight)
    end
end

//==============================================//
//                Output Block                  //
//==============================================//
// ouput valid
always @(posedge clk) begin
    if (current_state == READ && next_state == CACL) begin
        CNT_valid <= 1;
    end else begin
        CNT_valid <= 0;
    end
end

// output number of 6 characters
always @(posedge clk or posedge reset) begin
    if(reset) begin
        CNT1 <= 0;
        CNT2 <= 0;
        CNT3 <= 0;
        CNT4 <= 0;
        CNT5 <= 0;
        CNT6 <= 0;
    end else if (current_state == READ && next_state == CACL) begin
        CNT1 <= w[0];
        CNT2 <= w[1];
        CNT3 <= w[2];
        CNT4 <= w[3];
        CNT5 <= w[4];
        CNT6 <= w[5];
    end
end

// ouput valid
always @(posedge clk) begin
    if (current_state == OUT_CODE) begin
        code_valid <= 1;
    end else begin
        code_valid <= 0;
    end
end

// output Huffman code
always @(posedge clk or posedge reset) begin
    if(reset) begin
        HC1 <= 0;
        HC2 <= 0;
        HC3 <= 0;
        HC4 <= 0;
        HC5 <= 0;
        HC6 <= 0;
    end else if (current_state == OUT_CODE) begin
        HC1 <= code[0];
        HC2 <= code[1];
        HC3 <= code[2];
        HC4 <= code[3];
        HC5 <= code[4];
        HC6 <= code[5];
    end
end

// output mask for each character's Huffman code
always @(posedge clk or posedge reset) begin
    if(reset) begin
        M1 <= 0;
        M2 <= 0;
        M3 <= 0;
        M4 <= 0;
        M5 <= 0;
        M6 <= 0;
    end else if (current_state == OUT_CODE) begin
        // 11111111 = 0xff = 2^8-1 = 256-1 = 255
        M1 <= 8'b11111111 >> (8 - code_length[0]);
        M2 <= 8'b11111111 >> (8 - code_length[1]);
        M3 <= 8'b11111111 >> (8 - code_length[2]);
        M4 <= 8'b11111111 >> (8 - code_length[3]);
        M5 <= 8'b11111111 >> (8 - code_length[4]);
        M6 <= 8'b11111111 >> (8 - code_length[5]);
    end
end

endmodule

//================================================//
//            6-input sorting network             //
//================================================//
module sort_network (
    // Input character
    char0, char1, char2, char3, char4, char5,
    // Input weight
    w0, w1, w2, w3, w4, w5,
    // Output character
    out_char0, out_char1, out_char2, out_char3, out_char4, out_char5,
    // Output weight
    out_w0, out_w1, out_w2, out_w3, out_w4, out_w5
);

// 6 * 5-bit character
input [4:0] char0, char1, char2, char3, char4, char5;

// 6 * 8-bit weight
input [7:0] w0, w1, w2, w3, w4, w5;

// 6 * 5-bit character
output [4:0] out_char0, out_char1, out_char2, out_char3, out_char4, out_char5;

// 6 * 8-bit weight
output [7:0] out_w0, out_w1, out_w2, out_w3, out_w4, out_w5;

// 5-bit character
reg [4:0] out_char[0:5];

// 8-bit weight
reg [7:0] out_w[0:5];

// convert to array
assign out_char0 = out_char[0];
assign out_char1 = out_char[1];
assign out_char2 = out_char[2];
assign out_char3 = out_char[3];
assign out_char4 = out_char[4];
assign out_char5 = out_char[5];

assign out_w0 = out_w[0];
assign out_w1 = out_w[1];
assign out_w2 = out_w[2];
assign out_w3 = out_w[3];
assign out_w4 = out_w[4];
assign out_w5 = out_w[5];

// relation between two weight
wire relation01, relation02, relation03, relation04, relation05;
wire relation10, relation12, relation13, relation14, relation15;
wire relation20, relation21, relation23, relation24, relation25;
wire relation30, relation31, relation32, relation34, relation35;
wire relation40, relation41, relation42, relation43, relation45;
wire relation50, relation51, relation52, relation53, relation54;

assign relation01 = w0 < w1;
assign relation02 = w0 < w2;
assign relation03 = w0 < w3;
assign relation04 = w0 < w4;
assign relation05 = w0 < w5;

assign relation10 = ~relation01;
assign relation12 = w1 < w2;
assign relation13 = w1 < w3;
assign relation14 = w1 < w4;
assign relation15 = w1 < w5;

assign relation20 = ~relation02;
assign relation21 = ~relation12;
assign relation23 = w2 < w3;
assign relation24 = w2 < w4;
assign relation25 = w2 < w5;

assign relation30 = ~relation03;
assign relation31 = ~relation13;
assign relation32 = ~relation23;
assign relation34 = w3 < w4;
assign relation35 = w3 < w5;

assign relation40 = ~relation04;
assign relation41 = ~relation14;
assign relation42 = ~relation24;
assign relation43 = ~relation34;
assign relation45 = w4 < w5;

assign relation50 = ~relation05;
assign relation51 = ~relation15;
assign relation52 = ~relation25;
assign relation53 = ~relation35;
assign relation54 = ~relation45;

// calculate address
wire [2:0] addr0, addr1, addr2, addr3, addr4, addr5;
assign addr0 = relation01 + relation02 + relation03 + relation04 + relation05;
assign addr1 = relation10 + relation12 + relation13 + relation14 + relation15;
assign addr2 = relation20 + relation21 + relation23 + relation24 + relation25;
assign addr3 = relation30 + relation31 + relation32 + relation34 + relation35;
assign addr4 = relation40 + relation41 + relation42 + relation43 + relation45;
assign addr5 = relation50 + relation51 + relation52 + relation53 + relation54;

// output character
always @(*) begin
    out_char[5] = 0;
    out_char[4] = 0;
    out_char[3] = 0;
    out_char[2] = 0;
    out_char[1] = 0;
    out_char[0] = 0;
    out_char[addr0] = char0;
    out_char[addr1] = char1;
    out_char[addr2] = char2;
    out_char[addr3] = char3;
    out_char[addr4] = char4;
    out_char[addr5] = char5;
end

// output weight
always @(*) begin
    out_w[5] = 0;
    out_w[4] = 0;
    out_w[3] = 0;
    out_w[2] = 0;
    out_w[1] = 0;
    out_w[0] = 0;
    out_w[addr0] = w0;
    out_w[addr1] = w1;
    out_w[addr2] = w2;
    out_w[addr3] = w3;
    out_w[addr4] = w4;
    out_w[addr5] = w5;
end

endmodule

## syn.log
# Read all Files
read_verilog huffman.v
Loading db file '/home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/slow.db'
Loading db file '/home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/fast.db'
Loading db file '/usr/cad/synopsys/synthesis/2022.12/libraries/syn/dw_foundation.sldb'
Loading db file '/usr/cad/synopsys/synthesis/2022.12/libraries/syn/gtech.db'
Loading db file '/usr/cad/synopsys/synthesis/2022.12/libraries/syn/standard.sldb'
  Loading link library 'slow'
  Loading link library 'fast'
  Loading link library 'gtech'
Loading verilog file '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'
Detecting input file type automatically (-rtl or -netlist).
Reading with Presto HDL Compiler (equivalent to -rtl option).
Running PRESTO HDLC
Compiling source file /home/M12/chenneil90121/ic_contest_mock1/huffman.v
Warning:  /home/M12/chenneil90121/ic_contest_mock1/huffman.v:154: signed to unsigned assignment occurs. (VER-318)
Warning:  /home/M12/chenneil90121/ic_contest_mock1/huffman.v:181: signed to unsigned conversion occurs. (VER-318)

Statistics for case statements in always block at line 106 in file
        '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'
===============================================
|           Line           |  full/ parallel  |
===============================================
|           107            |    auto/auto     |
===============================================

Inferred memory devices in process
        in routine huffman line 98 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|  current_state_reg  | Flip-flop |   2   |  Y  | N  | Y  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 137 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|     counter_reg     | Flip-flop |   4   |  Y  | N  | Y  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 150 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|      code_reg       | Flip-flop |  48   |  Y  | N  | N  | N  | N  | N  | N  |
|   code_length_reg   | Flip-flop |  24   |  Y  | N  | N  | N  | N  | N  | N  |
|      head_reg       | Flip-flop |  24   |  Y  | N  | N  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 229 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|      char_reg       | Flip-flop |  30   |  Y  | N  | N  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 250 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|        w_reg        | Flip-flop |  48   |  Y  | N  | N  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 273 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|    CNT_valid_reg    | Flip-flop |   1   |  N  | N  | N  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 282 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|      CNT5_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|      CNT6_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|      CNT1_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|      CNT2_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|      CNT3_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|      CNT4_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 301 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|   code_valid_reg    | Flip-flop |   1   |  N  | N  | N  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 310 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|       HC5_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       HC6_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       HC1_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       HC2_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       HC3_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       HC4_reg       | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
===============================================================================

Inferred memory devices in process
        in routine huffman line 329 in file
                '/home/M12/chenneil90121/ic_contest_mock1/huffman.v'.
===============================================================================
|    Register Name    |   Type    | Width | Bus | MB | AR | AS | SR | SS | ST |
===============================================================================
|       M5_reg        | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       M6_reg        | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       M1_reg        | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       M2_reg        | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       M3_reg        | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
|       M4_reg        | Flip-flop |   8   |  Y  | N  | Y  | N  | N  | N  | N  |
===============================================================================
Presto compilation completed successfully.
Current design is now '/home/M12/chenneil90121/ic_contest_mock1/huffman.db:huffman'
Loaded 2 designs.
Current design is 'huffman'.
huffman sort_network
current_design huffman
Current design is 'huffman'.
{huffman}
link

  Linking design 'huffman'
  Using the following designs and libraries:
  --------------------------------------------------------------------------
  * (2 designs)               /home/M12/chenneil90121/ic_contest_mock1/huffman.db, etc
  slow (library)              /home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/slow.db
  fast (library)              /home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/fast.db
  dw_foundation.sldb (library) /usr/cad/synopsys/synthesis/2022.12/libraries/syn/dw_foundation.sldb

1
# Setting Clock Constraits
source -echo -verbose huffman.sdc
# operating conditions and boundary conditions #
set cycle  5.0        ;#clock period defined by designer
5.0
create_clock -period $cycle [get_ports  clk]
1
set_dont_touch_network      [get_clocks clk]
1
set_clock_uncertainty  0.1  [get_clocks clk]
1
set_clock_latency      0.5  [get_clocks clk]
1
set_input_delay  2.5      -clock clk [remove_from_collection [all_inputs] [get_ports clk]]
1
set_output_delay 0.5    -clock clk [all_outputs]
1
set_load         0.1     [all_outputs]
1
set_drive        1     [all_inputs]
1
set_operating_conditions  -max slow  -min fast
Using operating conditions 'slow' found in library 'slow'.
Using operating conditions 'fast' found in library 'fast'.
1
set_wire_load_model -name tsmc13_wl10 -library slow
1
set_max_fanout 20 [all_inputs]
1
1
# Synthesis all design
compile -map_effort high -area_effort high
Information: Checking out the license 'DesignWare'. (SEC-104)
Information: Evaluating DesignWare library utilization. (UISN-27)

============================================================================
| DesignWare Building Block Library  |         Version         | Available |
============================================================================
| Basic DW Building Blocks           | U-2022.12-DWBB_202212.0 |     *     |
| Licensed DW Building Blocks        | U-2022.12-DWBB_202212.0 |     *     |
============================================================================

====================================================================================================
| Flow Information                                                                                 |
----------------------------------------------------------------------------------------------------
| Flow         | Design Compiler NXT                                                               |
====================================================================================================
| Design Information                                      | Value                                  |
====================================================================================================
| Number of Scenarios                                     | 0                                      |
| Leaf Cell Count                                         | 1139                                   |
| Number of User Hierarchies                              | 1                                      |
| Sequential Cell Count                                   | 326                                    |
| Macro Count                                             | 0                                      |
| Number of Power Domains                                 | 0                                      |
| Number of Path Groups                                   | 2                                      |
| Number of VT Class                                      | 0                                      |
| Number of Clocks                                        | 1                                      |
| Number of Dont Touch Cells                              | 212                                    |
| Number of Dont Touch Nets                               | 1                                      |
| Number of Size Only Cells                               | 0                                      |
| Design with UPF Data                                    | false                                  |
====================================================================================================

Information: There are 16 potential problems in your design. Please run 'check_design' for more information. (LINT-99)


Warning: Operating condition slow set on design huffman has different process,
voltage and temperatures parameters than the parameters at which target library
fast is characterized. Delays may be inaccurate as a result. (OPT-998)

  Beginning Pass 1 Mapping
  ------------------------
  Processing 'sort_network'
  Processing 'huffman'
Information: Added key list 'DesignWare' to design 'huffman'. (DDB-72)
Information: The register 'char_reg[4][4]' is a constant and will be removed. (OPT-1206)
Information: The register 'char_reg[4][2]' is a constant and will be removed. (OPT-1206)

  Updating timing information
Information: Updating design information... (UID-85)

  Beginning Implementation Selection
  ----------------------------------
  Mapping 'DW_rightsh'
  Processing 'huffman_DW01_sub_0'
  Mapping 'DW_rightsh'
  Processing 'huffman_DW01_sub_1'
  Mapping 'DW_rightsh'
  Processing 'huffman_DW01_sub_2'
  Mapping 'DW_rightsh'
  Processing 'huffman_DW01_sub_3'
  Mapping 'DW_rightsh'
  Processing 'huffman_DW01_sub_4'
  Mapping 'DW_rightsh'
  Processing 'huffman_DW01_sub_5'
  Processing 'huffman_DW01_inc_0_DW01_inc_7'
  Processing 'huffman_DW01_add_0'
  Processing 'huffman_DW01_add_1'
  Mapping 'DW_leftsh'
  Processing 'huffman_DW01_add_2'
  Mapping 'DW_leftsh'
  Processing 'huffman_DW01_add_3'
  Mapping 'DW_leftsh'
  Processing 'huffman_DW01_add_4'
  Mapping 'DW_leftsh'
  Processing 'huffman_DW01_add_5'
  Mapping 'DW_leftsh'
  Processing 'huffman_DW01_add_6'
  Mapping 'DW_leftsh'
  Processing 'huffman_DW01_add_7'
  Mapping 'sort_network_DW_cmp_0'
  Mapping 'sort_network_DW_cmp_1'
  Mapping 'sort_network_DW_cmp_2'
  Mapping 'sort_network_DW_cmp_3'
  Mapping 'sort_network_DW_cmp_4'
  Mapping 'sort_network_DW_cmp_5'
  Mapping 'sort_network_DW_cmp_6'
  Mapping 'sort_network_DW_cmp_7'
  Mapping 'sort_network_DW_cmp_8'
  Mapping 'sort_network_DW_cmp_9'
  Mapping 'sort_network_DW_cmp_10'
  Mapping 'sort_network_DW_cmp_11'
  Mapping 'sort_network_DW_cmp_12'
  Mapping 'sort_network_DW_cmp_13'
  Mapping 'sort_network_DW_cmp_14'
  Building model 'DW01_NAND2'
  Processing 'DW01_NAND2'
  Building model 'DW01_add_width2' (rpl)
  Processing 'DW01_add_width2'
  Building model 'DW01_add_width3' (rpl)
  Processing 'DW01_add_width3'
  Processing 'DW01_add_width3_DW01_add_8'
  Processing 'DW01_add_width2_DW01_add_9'
  Processing 'DW01_add_width3_DW01_add_10'
  Processing 'DW01_add_width2_DW01_add_11'
  Processing 'DW01_add_width3_DW01_add_12'
  Processing 'DW01_add_width2_DW01_add_13'
  Processing 'DW01_add_width3_DW01_add_14'
  Processing 'DW01_add_width2_DW01_add_15'
  Processing 'DW01_add_width3_DW01_add_16'
  Processing 'DW01_add_width2_DW01_add_17'
  Processing 'DW01_add_width3_DW01_add_18'
  Processing 'DW01_add_width2_DW01_add_19'

  Beginning Mapping Optimizations  (High effort)
  -------------------------------
Information: Added key list 'DesignWare' to design 'sort_network'. (DDB-72)
Loading db file '/home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/fast.db'
  Mapping Optimization (Phase 1)
  Mapping Optimization (Phase 2)
  Mapping Optimization (Phase 3)
  Mapping Optimization (Phase 4)
  Mapping Optimization (Phase 5)
  Mapping Optimization (Phase 6)
  Mapping Optimization (Phase 7)

                                  TOTAL
   ELAPSED            WORST NEG   SETUP    DESIGN
    TIME      AREA      SLACK     COST    RULE COST         ENDPOINT
  --------- --------- --------- --------- --------- -------------------------
    0:00:20   56835.7      0.16      13.2      46.3
    0:00:20   57083.6      0.17      17.5      46.3
    0:00:20   57083.6      0.17      17.5      46.3
    0:00:20   57059.8      0.17      17.5      46.3
    0:00:20   57059.8      0.17      17.5      46.3
    0:00:21   35533.4      3.94     486.6       0.0
    0:00:22   36105.4      3.47     476.5       0.0
    0:00:22   36129.2      3.45     437.2       0.0
    0:00:22   36107.1      3.34     431.6       0.0
    0:00:22   36054.5      3.45     451.9       0.0
    0:00:23   36171.6      2.96     395.3       0.0
    0:00:23   36105.4      3.22     405.2       0.0
    0:00:23   36102.0      2.70     380.9       0.0
    0:00:23   36141.0      2.55     349.8       0.0
    0:00:23   36083.3      2.40     340.8       0.0
    0:00:23   36175.0      2.37     333.6       0.0
    0:00:23   36222.5      2.33     322.6       0.0
    0:00:23   36348.1      2.30     319.7       0.0
    0:00:23   36360.0      2.21     311.8       0.0
    0:00:23   36421.1      2.16     310.5       0.0
    0:00:23   36533.1      2.14     306.4       0.0
    0:00:23   36536.5      2.13     306.2       0.0
    0:00:23   36584.1      2.10     304.7       0.0
    0:00:24   36604.4      2.09     303.4       0.0
    0:00:24   36604.4      2.09     303.4       0.0
    0:00:24   36604.4      2.09     303.4       0.0
    0:00:24   36604.4      2.09     303.4       0.0
    0:00:24   36604.4      2.09     303.4       0.0
    0:00:24   36604.4      2.09     303.4       0.0
    0:00:24   36999.9      1.68     249.6       0.0 w_reg[1][1]/D
    0:00:24   37347.9      1.37     205.8      85.6 w_reg[1][3]/D
    0:00:24   37570.3      1.17     177.1     171.3 code_reg[3][4]/D
    0:00:25   37734.9      1.11     168.7     171.3 code_reg[3][4]/D
    0:00:25   37999.7      1.04     159.8     176.2 code_reg[3][4]/D
    0:00:25   38868.8      0.94     144.8     181.4 code_reg[4][4]/D
    0:00:26   40937.9      0.73     112.9     193.8 code_reg[1][4]/D
    0:00:26   41448.8      0.63      96.2     216.4 code_reg[1][4]/D
    0:00:27   42024.2      0.59      88.3     216.4 code_reg[3][4]/D
    0:00:27   42314.5      0.55      81.8     305.2 code_reg[2][5]/D
    0:00:27   42339.9      0.53      77.6     311.4 code_reg[2][5]/D
    0:00:27   42604.7      0.51      75.3     283.6 code_reg[2][4]/D
    0:00:28   42764.3      0.48      71.7     283.6 code_reg[1][4]/D
    0:00:28   42968.0      0.45      64.8     331.1 code_length_reg[3][3]/D
    0:00:28   43073.2      0.43      62.2     331.1 code_reg[1][4]/D
    0:00:28   43236.2      0.41      60.3     331.1 code_reg[1][4]/D
    0:00:28   43351.6      0.39      57.7     344.1 code_reg[1][4]/D
    0:00:29   43378.8      0.38      56.4     344.1 code_reg[1][4]/D
    0:00:29   43501.0      0.38      54.1     344.1 code_reg[1][4]/D
    0:00:29   43463.6      0.36      51.4     344.1 code_reg[1][4]/D
    0:00:29   43528.1      0.35      36.5     344.1 code_reg[1][4]/D
    0:00:29   43565.5      0.34      33.3     344.1 code_reg[1][4]/D
    0:00:30   43548.5      0.33      32.7     343.8 code_reg[1][4]/D
    0:00:30   43669.0      0.31      30.0     343.8 code_reg[1][4]/D
    0:00:30   43696.2      0.30      29.1     343.8 code_reg[1][4]/D
    0:00:31   44045.8      0.25      24.8     343.8
    0:00:31   44222.4      0.23      21.8     343.8
    0:00:31   44336.1      0.22      18.3     346.3
    0:00:31   44466.8      0.20      17.0     346.3
    0:00:31   44533.0      0.20      15.7     346.3
    0:00:31   44548.3      0.19      14.5     346.3
    0:00:31   44656.9      0.16      11.4     366.5
    0:00:31   44763.8      0.14      10.1     366.5
    0:00:32   44828.3      0.13       8.5     366.5
    0:00:32   45113.5      0.07       4.3     359.5
    0:00:32   45127.1      0.06       3.2     358.9
    0:00:32   45235.7      0.05       2.1     377.8
    0:00:32   45317.2      0.05       1.5     391.3
    0:00:32   45320.6      0.05       1.2     396.0


  Beginning Delay Optimization Phase
  ----------------------------------

                                  TOTAL
   ELAPSED            WORST NEG   SETUP    DESIGN
    TIME      AREA      SLACK     COST    RULE COST         ENDPOINT
  --------- --------- --------- --------- --------- -------------------------
    0:00:32   45320.6      0.05       1.2     396.0
    0:00:32   45463.2      0.01       0.1     399.5 w_reg[2][6]/D
    0:00:33   45451.3      0.00       0.0     399.5 w_reg[2][4]/D
    0:00:33   45444.5      0.00       0.0     399.5 w_reg[5][7]/D
    0:00:33   45424.1      0.00       0.0     399.5 w_reg[2][6]/D
    0:00:33   45432.6      0.00       0.0     399.5
    0:00:34   45354.5      0.00       0.0     402.7


  Beginning Design Rule Fixing  (max_transition)  (max_capacitance)
  ----------------------------

                                  TOTAL
   ELAPSED            WORST NEG   SETUP    DESIGN
    TIME      AREA      SLACK     COST    RULE COST         ENDPOINT
  --------- --------- --------- --------- --------- -------------------------
    0:00:34   45354.5      0.00       0.0     402.7
    0:00:34   45111.8      0.00       0.0       0.0


  Beginning Area-Recovery Phase  (cleanup)
  -----------------------------

                                  TOTAL
   ELAPSED            WORST NEG   SETUP    DESIGN
    TIME      AREA      SLACK     COST    RULE COST         ENDPOINT
  --------- --------- --------- --------- --------- -------------------------
    0:00:34   45111.8      0.00       0.0       0.0
    0:00:34   45111.8      0.00       0.0       0.0
    0:00:34   43920.2      0.13       4.4       0.0
    0:00:34   43533.2      0.13       4.5       0.0
    0:00:35   43392.3      0.13       4.4       0.0
    0:00:35   43365.2      0.13       4.4       0.0
    0:00:35   43344.8      0.13       4.4       0.0
    0:00:35   43344.8      0.13       4.4       0.0
    0:00:35   43356.7      0.01       0.2       0.0 head_reg[5][1]/D
    0:00:35   43332.9      0.00       0.0       0.0
    0:00:35   43331.2      0.00       0.0       0.0
    0:00:35   40871.7      1.34      87.1       0.0
    0:00:35   40225.0      1.71     141.8       0.0
    0:00:36   40158.8      1.70     139.7       0.0
    0:00:36   40153.7      1.70     139.7       0.0
    0:00:36   40153.7      1.70     139.7       0.0
    0:00:36   40153.7      1.70     139.7       0.0
    0:00:36   40153.7      1.70     139.7       0.0
    0:00:36   40153.7      1.70     139.7       0.0
    0:00:36   40708.7      0.29      32.3       0.0 head_reg[0][2]/D
    0:00:36   40932.8      0.18      15.0       0.0 w_reg[1][1]/D
    0:00:36   41133.1      0.13       9.4       0.0 code_reg[5][0]/D
    0:00:36   41309.6      0.09       5.5       0.0 code_reg[5][0]/D
    0:00:37   41426.7      0.09       5.5       0.0 code_reg[5][0]/D
    0:00:37   41499.7      0.05       1.5       0.0 code_reg[2][7]/D
    0:00:37   41642.3      0.03       0.7       0.0 code_reg[1][3]/D
    0:00:37   41582.9      0.01       0.3       0.0
    0:00:38   41635.5      0.00       0.0       0.0
    0:00:38   41644.0      0.00       0.0       0.0
Loading db file '/home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/slow.db'


Note: Symbol # after min delay cost means estimated hold TNS across all active scenarios


  Optimization Complete
  ---------------------
1
compile -map_effort high -area_effort high -inc
====================================================================================================
| Flow Information                                                                                 |
----------------------------------------------------------------------------------------------------
| Flow         | Design Compiler NXT                                                               |
====================================================================================================
| Design Information                                      | Value                                  |
====================================================================================================
| Number of Scenarios                                     | 0                                      |
| Leaf Cell Count                                         | 2711                                   |
| Number of User Hierarchies                              | 9                                      |
| Sequential Cell Count                                   | 324                                    |
| Macro Count                                             | 0                                      |
| Number of Power Domains                                 | 0                                      |
| Number of Path Groups                                   | 2                                      |
| Number of VT Class                                      | 0                                      |
| Number of Clocks                                        | 1                                      |
| Number of Dont Touch Cells                              | 0                                      |
| Number of Dont Touch Nets                               | 1                                      |
| Number of Size Only Cells                               | 0                                      |
| Design with UPF Data                                    | false                                  |
====================================================================================================

Information: There are 23 potential problems in your design. Please run 'check_design' for more information. (LINT-99)


Warning: Operating condition slow set on design huffman has different process,
voltage and temperatures parameters than the parameters at which target library
fast is characterized. Delays may be inaccurate as a result. (OPT-998)

  Beginning Pass 1 Mapping  (Incremental)
  ------------------------

  Updating timing information
Information: Updating design information... (UID-85)

  Beginning Mapping Optimizations  (High effort)  (Incremental)
  -------------------------------

  Beginning Incremental Implementation Selection
  ----------------------------------------------
  Mapping 'huffman_DW01_inc_0'
  Mapping 'huffman_DW01_add_0'
  Selecting implementations
  Building model 'DW01_NAND2'
  Building model 'DW01_add_width8' (rpl)

  Beginning Delay Optimization Phase
  ----------------------------------

                                  TOTAL
   ELAPSED            WORST NEG   SETUP    DESIGN
    TIME      AREA      SLACK     COST    RULE COST         ENDPOINT
  --------- --------- --------- --------- --------- -------------------------
    0:00:01   41644.0      0.00       0.0       0.0
    0:00:01   41644.0      0.00       0.0       0.0
    0:00:02   40849.6      0.00       0.0    5541.6


  Beginning Design Rule Fixing  (max_transition)  (max_capacitance)
  ----------------------------

                                  TOTAL
   ELAPSED            WORST NEG   SETUP    DESIGN
    TIME      AREA      SLACK     COST    RULE COST         ENDPOINT
  --------- --------- --------- --------- --------- -------------------------
    0:00:02   40849.6      0.00       0.0    5541.6
    0:00:02   41083.9      0.00       0.0    3585.8 CNT6[2]
    0:00:02   41307.9      0.00       0.0    1785.6 M6[6]
    0:00:02   41549.0      0.00       0.0     191.0 CNT4[1]
    0:00:02   41584.6      0.00       0.0       0.0
Loading db file '/home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/fast.db'
Loading db file '/home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/slow.db'


Note: Symbol # after min delay cost means estimated hold TNS across all active scenarios


  Optimization Complete
  ---------------------
1
write -format ddc  -hierarchy -output "huffman_syn.ddc"
Writing ddc file 'huffman_syn.ddc'.
1
write_sdf huffman_syn.sdf
Information: Annotated 'cell' delays are assumed to include load delay. (UID-282)
Information: Writing timing information to file '/home/M12/chenneil90121/ic_contest_mock1/huffman_syn.sdf'. (WT-3)
Information: Updating design information... (UID-85)
1
write_file -format verilog -hierarchy -output huffman_syn.v
Writing verilog file '/home/M12/chenneil90121/ic_contest_mock1/huffman_syn.v'.
Warning: Verilog 'assign' or 'tran' statements are written out. (VO-4)
1
report_area > area.log
report_timing > timing.log
report_qor > huffman_syn.qor
report_area -designware -hierarchy

****************************************
Report : area
Design : huffman
Version: U-2022.12
Date   : Tue Mar 19 02:42:43 2024
****************************************

Library(s) Used:

    slow (File: /home/cell_library/CBDK_IC_Contest_v2.5/SynopsysDC/db/slow.db)

Number of ports:                          511
Number of nets:                          3175
Number of cells:                         2754
Number of combinational cells:           2382
Number of sequential cells:               324
Number of macros/black boxes:               0
Number of buf/inv:                        648
Number of references:                     153

Combinational area:              29789.369965
Buf/Inv area:                     5791.528802
Noncombinational area:           11795.232740
Macro/Black Box area:                0.000000
Net Interconnect area:          324428.314148

Total cell area:                 41584.602705
Total area:                     366012.916853

Hierarchical area distribution
------------------------------

                                  Global cell area            Local cell area
                                  -------------------  ------------------------------
Hierarchical cell                 Absolute    Percent  Combi-      Noncombi-   Black-
                                  Total       Total    national    national    boxes   Design
--------------------------------  ----------  -------  ----------  ----------  ------  ---------------------
huffman                           41584.6027    100.0  12603.1949  11795.2327  0.0000  huffman
add_181                             383.6124      0.9    383.6124      0.0000  0.0000  huffman_DW01_add_6
add_181_I2                          383.6124      0.9    383.6124      0.0000  0.0000  huffman_DW01_add_5
add_181_I3                          420.9552      1.0    420.9552      0.0000  0.0000  huffman_DW01_add_4
add_181_I4                          329.2956      0.8    329.2956      0.0000  0.0000  huffman_DW01_add_3
add_181_I5                          358.1514      0.9    358.1514      0.0000  0.0000  huffman_DW01_add_2
add_181_I6                          388.7046      0.9    388.7046      0.0000  0.0000  huffman_DW01_add_1
add_223                             575.4186      1.4    575.4186      0.0000  0.0000  huffman_DW01_add_8
add_257                             500.7330      1.2    500.7330      0.0000  0.0000  huffman_DW01_inc_J1_0
s0                                13845.6918     33.3  13845.6918      0.0000  0.0000  sort_network
--------------------------------  ----------  -------  ----------  ----------  ------  ---------------------
Total                                                  29789.3700  11795.2327  0.0000


Area of detected synthetic parts
--------------------------------
                                      Perc. of
  Module   Implem.  Count       Area cell area
  -------- -------  ----- ---------- ---------
  DW01_add  pparch      1   575.4186      1.4%
  DW01_add     rpl      6  2264.3316      5.4%
  DW01_inc  pparch      1   500.7330      1.2%
  -------- -------  ----- ---------- ---------
  Total:                8  3340.4832      8.0%

Estimated area of ungrouped synthetic parts
-------------------------------------------
                             Estimated  Perc. of
  Module     Implem.  Count       Area cell area
  ---------- -------  ----- ---------- ---------
  DW01_add       rpl     13   694.4656      1.7%
  DW01_dec       rpl      1    32.2506      0.1%
  DW01_inc       rpl      7   356.4540      0.9%
  DW01_sub       rpl      6  1763.6835      4.2%
  DW_cmp     apparch     27  2997.5661      7.2%
  DW_leftsh     astr      6   488.8512      1.2%
  DW_rightsh    astr      6   529.5888      1.3%
  ---------- -------  ----- ---------- ---------
  Total:                 66  6862.8597     16.5%

Total synthetic cell area:              10203.3429  24.5%  (estimated)

1
report_timing

****************************************
Report : timing
        -path full
        -delay max
        -max_paths 1
Design : huffman
Version: U-2022.12
Date   : Tue Mar 19 02:42:43 2024
****************************************

Operating Conditions: slow   Library: slow
Wire Load Model Mode: top

  Startpoint: w_reg[2][5]
              (rising edge-triggered flip-flop clocked by clk)
  Endpoint: code_reg[0][7]
            (rising edge-triggered flip-flop clocked by clk)
  Path Group: clk
  Path Type: max

  Des/Clust/Port     Wire Load Model       Library
  ------------------------------------------------
  huffman            tsmc13_wl10           slow

  Point                                    Incr       Path
  -----------------------------------------------------------
  clock clk (rise edge)                    0.00       0.00
  clock network delay (ideal)              0.50       0.50
  w_reg[2][5]/CK (DFFHQX8)                 0.00       0.50 r
  w_reg[2][5]/Q (DFFHQX8)                  0.24       0.74 f
  s0/w2[5] (sort_network)                  0.00       0.74 f
  s0/U172/Y (BUFX20)                       0.18       0.91 f
  s0/U82/Y (INVX20)                        0.10       1.02 r
  s0/U568/Y (NAND2X6)                      0.08       1.10 f
  s0/U177/Y (AND2X2)                       0.21       1.30 f
  s0/U134/Y (AND2X4)                       0.18       1.48 f
  s0/U193/Y (OR2X4)                        0.19       1.67 f
  s0/U130/Y (NAND3X6)                      0.10       1.77 r
  s0/U299/Y (NAND4X8)                      0.19       1.95 f
  s0/U26/Y (XOR3X4)                        0.47       2.42 f
  s0/U131/Y (XNOR3X4)                      0.31       2.73 f
  s0/U81/Y (CLKINVX8)                      0.13       2.86 r
  s0/U605/Y (AND3X8)                       0.15       3.01 r
  s0/U446/Y (AND4X8)                       0.18       3.19 r
  s0/U582/Y (INVX16)                       0.07       3.27 f
  s0/U953/Y (AOI2BB2X4)                    0.20       3.47 f
  s0/U1041/Y (OAI211X2)                    0.21       3.68 r
  s0/out_char4[3] (sort_network)           0.00       3.68 r
  U789/Y (INVX12)                          0.16       3.84 f
  U1240/Y (XOR2X4)                         0.25       4.09 r
  U1088/Y (NAND2X6)                        0.11       4.19 f
  U1142/Y (NOR4BX4)                        0.20       4.40 r
  U1929/Y (OAI31X2)                        0.16       4.56 f
  U1094/Y (BUFX16)                         0.20       4.75 f
  U1328/Y (AOI32X4)                        0.47       5.22 r
  U1327/Y (INVX4)                          0.05       5.27 f
  code_reg[0][7]/D (DFFRHQX4)              0.00       5.27 f
  data arrival time                                   5.27

  clock clk (rise edge)                    5.00       5.00
  clock network delay (ideal)              0.50       5.50
  clock uncertainty                       -0.10       5.40
  code_reg[0][7]/CK (DFFRHQX4)             0.00       5.40 r
  library setup time                      -0.13       5.27
  data required time                                  5.27
  -----------------------------------------------------------
  data required time                                  5.27
  data arrival time                                  -5.27
  -----------------------------------------------------------
  slack (MET)                                         0.00


1
exit
Memory usage for this session 244 Mbytes.
Memory usage for this session including child processes 358 Mbytes.
CPU usage for this session 80 seconds ( 0.02 hours ).
Elapsed time for this session 50 seconds ( 0.01 hours ).

Thank you...
	//############################################################################
	// 2018 IC Contest graduate group preliminary round
	// Topic : Huffman Coding
	// Author : HsuChiChen (chenneil90121@gmail.com)
	//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	// Date : 2024.02.24
	// Version : v1.0
	// File Name : huffman.v
	// Module Name : huffman
	//############################################################################
	// Huffman coding is a method of lossless data compression.
	// It assigns variable-length codes to input characters, the length of the code depends on the frequency of the character.
	// The most frequent character gets the smallest code and the least frequent character gets the largest code.
	// The codes are prefix-free, which means that no code is a prefix of another code.
	// This is useful for decoding, as it means that the code can be read one bit at a time and the result will be unambiguous.

	// My algorithm is as follows:
	// 1. count the number of 6 character from gray image in 100 cycles
	// 2. sort the 6 character and 6 weight in 5 cycles. Simulatuously, calculate the Huffman code and code length
	// Do not need to establish Huffman tree, just use the pointer to top node for node 0 ~ 5
	// 3. output the number of 6 characters, Huffman code, and mask for each character's Huffman code in 1 cycle

	// In TSMC 0.13um technology, latency is 5 cycles
	// when cycle time is 5ns, total cell area 41584 um^2
	// when cycle time is 6ns, total cell area 35080 um^2
	// when cycle time is 10ns, total cell area 26710 um^2

	module huffman(
	// Input Ports
	clk, reset, gray_valid, gray_data, CNT_valid,
	// Output Ports
	CNT1, CNT2, CNT3, CNT4, CNT5, CNT6, // number of 6 characters (symbol)
	code_valid, HC1, HC2, HC3, HC4, HC5, HC6, // each character's Huffman code
	M1, M2, M3, M4, M5, M6); // mask for each character's Huffman code

	//==============================================//
	// Input & Output Declaration //
	//==============================================//
	// Input Ports
	input clk;
	input reset;
	input gray_valid;
	input [7:0] gray_data;

	// Output Ports
	output reg CNT_valid;
	output reg [7:0] CNT1, CNT2, CNT3, CNT4, CNT5, CNT6;
	output reg code_valid;
	output reg [7:0] HC1, HC2, HC3, HC4, HC5, HC6;
	output reg [7:0] M1, M2, M3, M4, M5, M6;

	//==============================================//
	// Parameter and Integer //
	//==============================================//
	parameter IDLE = 0,
	READ = 1,
	CACL = 2,
	OUT_CODE = 3;

	integer i;
	//==============================================//
	// reg declaration //
	//==============================================//
	// state machine
	reg [1:0] current_state;

	// state counter
	reg [3:0] counter;

	// pointer to top node
	reg [3:0] head[0:5];

	// 8-bit huffman code
	reg [7:0] code[0:5];

	// 4-bit code length
	reg [3:0] code_length[0:5];

	// input character
	reg [4:0] char[0:5];

	// image counter
	reg [7:0] image_counter[0:5];

	// input weight
	reg [7:0] w[0:5];

	//==============================================//
	// psedo-reg wire declaration //
	//==============================================//
	// state machine
	reg [1:0] next_state;

	// sort network output
	wire [4:0] out_char[0:5];
	wire [7:0] out_w[0:5];

	// sum of two weight
	wire [7:0] out_w_sum;

	//==============================================//
	// Current State Block //
	//==============================================//
	always @(posedge clk or posedge reset) begin
	if(reset) current_state <= IDLE;
	else current_state <= next_state;
	end

	//==============================================//
	// Next State Block //
	//==============================================//
	always @(*) begin
	case (current_state)
	// wait for read gray image
	IDLE: begin
	if (gray_valid) next_state = READ;
	else next_state = IDLE;
	end

	// read gray image with 100 cycles
	READ: begin
	if (gray_valid) next_state = READ;
	else next_state = CACL;
	end

	// 5 cycles calculate 6 weight
	CACL: begin
	if (counter == 4) next_state = OUT_CODE;
	else next_state = CACL;
	end

	// output Huffman code in one cycle
	OUT_CODE : begin
	next_state = IDLE;
	end
	default: next_state = IDLE; // illegal state
	endcase
	end

	//==============================================//
	// Counter for 5 cycles in CACL state //
	//==============================================//
	always @(posedge clk or posedge reset) begin
	if(reset) begin
	counter <= 0;
	end else if (current_state == CACL) begin
	counter <= counter + 1;
	end else begin
	counter <= 0;
	end
	end

	//==================================================//
	// Pointer to top node, Huffman code, code length //
	//==================================================//
	always @(posedge clk) begin
	if(current_state == READ) begin
	// initialize top node as node 0 ~ 5 itself
	for(i = 0; i < 6; i = i + 1) begin
	head[i] <= i;
	end

	// initialize Huffman code as 0
	for(i = 0; i < 6; i = i + 1) begin
	code[i] <= 0;
	end

	// initialize code length as 0
	for(i = 0; i < 6; i = i + 1) begin
	code_length[i] <= 0;
	end

	// The node with the 2nd smallest / 1st smallest weight will compare with node 0 ~ 5
	// If match the node, those node will update its pointer to top pointer
	// simultaneously, the Huffman code will add 0 / 1 in the front
	end else if(current_state == CACL) begin
	for(i = 0; i < 6; i = i + 1) begin
	// 2nd smallest be left child of top node, Huffman code add 0
	if(head[i] == out_char[4]) begin
	head[i] <= counter + 6; // update pointer to top pointer
	// code[i] <= (code[i] << 1) + 0; // Huffman code = 0
	code_length[i] <= code_length[i] + 1; // Huffman code length + 1

	// 1st smallest be right child of top node, Huffman code add 1
	end else if(head[i] == out_char[5]) begin
	head[i] <= counter + 6; // update pointer to top pointer
	code[i] <= code[i] + (1 << code_length[i]); // Huffman code = 1
	code_length[i] <= code_length[i] + 1; // Huffman code length + 1
	end
	end
	end
	end

	//==============================================//
	// sorting module //
	//==============================================//
	sort_network s0(
	// Input character
	.char0(char[0]),
	.char1(char[1]),
	.char2(char[2]),
	.char3(char[3]),
	.char4(char[4]),
	.char5(char[5]),
	// Input weight
	.w0(w[0]),
	.w1(w[1]),
	.w2(w[2]),
	.w3(w[3]),
	.w4(w[4]),
	.w5(w[5]),
	// Output character
	.out_char0(out_char[0]),
	.out_char1(out_char[1]),
	.out_char2(out_char[2]),
	.out_char3(out_char[3]),
	.out_char4(out_char[4]),
	.out_char5(out_char[5]),
	// Output weight
	.out_w0(out_w[0]),
	.out_w1(out_w[1]),
	.out_w2(out_w[2]),
	.out_w3(out_w[3]),
	.out_w4(out_w[4]),
	.out_w5(out_w[5])
	);

	// sum of two weight
	assign out_w_sum = out_w[4] + out_w[5];

	//==============================================//
	// input character & weight //
	//==============================================//
	// input character
	always @(posedge clk) begin
	// initialize character
	if(current_state == READ) begin
	char[0] <= 0;
	char[1] <= 1;
	char[2] <= 2;
	char[3] <= 3;
	char[4] <= 4;
	char[5] <= 5;
	// 5 cycles sort 6 character
	end else if(current_state == CACL) begin
	char[0] <= out_char[0];
	char[1] <= out_char[1];
	char[2] <= out_char[2];
	char[3] <= out_char[3];
	char[4] <= 15; // unused node
	char[5] <= counter + 6; // add new node named 6, 7, 8, 9, 10 (counter from 0 to 4)
	end
	end

	// input weight
	always @(posedge clk) begin
	if(reset) begin
	for (i = 0; i < 6; i = i + 1) begin
	w[i] <= 0;
	end
	// count the frequency of each character from gray image with 100 cycles
	end else if (gray_valid) begin
	w[gray_data - 1] <= w[gray_data - 1] + 1;
	// 5 cycles sort 6 weight
	end else if(current_state == CACL) begin
	w[0] <= out_w[0];
	w[1] <= out_w[1];
	w[2] <= out_w[2];
	w[3] <= out_w[3];
	w[4] <= 255; // unused weight
	w[5] <= out_w_sum; // add new weight (sum of 2 smallest weight)
	end
	end

	//==============================================//
	// Output Block //
	//==============================================//
	// ouput valid
	always @(posedge clk) begin
	if (current_state == READ && next_state == CACL) begin
	CNT_valid <= 1;
	end else begin
	CNT_valid <= 0;
	end
	end

	// output number of 6 characters
	always @(posedge clk or posedge reset) begin
	if(reset) begin
	CNT1 <= 0;
	CNT2 <= 0;
	CNT3 <= 0;
	CNT4 <= 0;
	CNT5 <= 0;
	CNT6 <= 0;
	end else if (current_state == READ && next_state == CACL) begin
	CNT1 <= w[0];
	CNT2 <= w[1];
	CNT3 <= w[2];
	CNT4 <= w[3];
	CNT5 <= w[4];
	CNT6 <= w[5];
	end
	end

	// ouput valid
	always @(posedge clk) begin
	if (current_state == OUT_CODE) begin
	code_valid <= 1;
	end else begin
	code_valid <= 0;
	end
	end

	// output Huffman code
	always @(posedge clk or posedge reset) begin
	if(reset) begin
	HC1 <= 0;
	HC2 <= 0;
	HC3 <= 0;
	HC4 <= 0;
	HC5 <= 0;
	HC6 <= 0;
	end else if (current_state == OUT_CODE) begin
	HC1 <= code[0];
	HC2 <= code[1];
	HC3 <= code[2];
	HC4 <= code[3];
	HC5 <= code[4];
	HC6 <= code[5];
	end
	end

	// output mask for each character's Huffman code
	always @(posedge clk or posedge reset) begin
	if(reset) begin
	M1 <= 0;
	M2 <= 0;
	M3 <= 0;
	M4 <= 0;
	M5 <= 0;
	M6 <= 0;
	end else if (current_state == OUT_CODE) begin
	// 11111111 = 0xff = 2^8-1 = 256-1 = 255
	M1 <= 8'b11111111 >> (8 - code_length[0]);
	M2 <= 8'b11111111 >> (8 - code_length[1]);
	M3 <= 8'b11111111 >> (8 - code_length[2]);
	M4 <= 8'b11111111 >> (8 - code_length[3]);
	M5 <= 8'b11111111 >> (8 - code_length[4]);
	M6 <= 8'b11111111 >> (8 - code_length[5]);
	end
	end

	endmodule

	//================================================//
	// 6-input sorting network //
	//================================================//
	module sort_network (
	// Input character
	char0, char1, char2, char3, char4, char5,
	// Input weight
	w0, w1, w2, w3, w4, w5,
	// Output character
	out_char0, out_char1, out_char2, out_char3, out_char4, out_char5,
	// Output weight
	out_w0, out_w1, out_w2, out_w3, out_w4, out_w5
	);

	// 6 * 5-bit character
	input [4:0] char0, char1, char2, char3, char4, char5;

	// 6 * 8-bit weight
	input [7:0] w0, w1, w2, w3, w4, w5;

	// 6 * 5-bit character
	output [4:0] out_char0, out_char1, out_char2, out_char3, out_char4, out_char5;

	// 6 * 8-bit weight
	output [7:0] out_w0, out_w1, out_w2, out_w3, out_w4, out_w5;

	// 5-bit character
	reg [4:0] out_char[0:5];

	// 8-bit weight
	reg [7:0] out_w[0:5];

	// convert to array
	assign out_char0 = out_char[0];
	assign out_char1 = out_char[1];
	assign out_char2 = out_char[2];
	assign out_char3 = out_char[3];
	assign out_char4 = out_char[4];
	assign out_char5 = out_char[5];

	assign out_w0 = out_w[0];
	assign out_w1 = out_w[1];
	assign out_w2 = out_w[2];
	assign out_w3 = out_w[3];
	assign out_w4 = out_w[4];
	assign out_w5 = out_w[5];

	// relation between two weight
	wire relation01, relation02, relation03, relation04, relation05;
	wire relation10, relation12, relation13, relation14, relation15;
	wire relation20, relation21, relation23, relation24, relation25;
	wire relation30, relation31, relation32, relation34, relation35;
	wire relation40, relation41, relation42, relation43, relation45;
	wire relation50, relation51, relation52, relation53, relation54;

	assign relation01 = w0 < w1;
	assign relation02 = w0 < w2;
	assign relation03 = w0 < w3;
	assign relation04 = w0 < w4;
	assign relation05 = w0 < w5;

	assign relation10 = ~relation01;
	assign relation12 = w1 < w2;
	assign relation13 = w1 < w3;
	assign relation14 = w1 < w4;
	assign relation15 = w1 < w5;

	assign relation20 = ~relation02;
	assign relation21 = ~relation12;
	assign relation23 = w2 < w3;
	assign relation24 = w2 < w4;
	assign relation25 = w2 < w5;

	assign relation30 = ~relation03;
	assign relation31 = ~relation13;
	assign relation32 = ~relation23;
	assign relation34 = w3 < w4;
	assign relation35 = w3 < w5;

	assign relation40 = ~relation04;
	assign relation41 = ~relation14;
	assign relation42 = ~relation24;
	assign relation43 = ~relation34;
	assign relation45 = w4 < w5;

	assign relation50 = ~relation05;
	assign relation51 = ~relation15;
	assign relation52 = ~relation25;
	assign relation53 = ~relation35;
	assign relation54 = ~relation45;

	// calculate address
	wire [2:0] addr0, addr1, addr2, addr3, addr4, addr5;
	assign addr0 = relation01 + relation02 + relation03 + relation04 + relation05;
	assign addr1 = relation10 + relation12 + relation13 + relation14 + relation15;
	assign addr2 = relation20 + relation21 + relation23 + relation24 + relation25;
	assign addr3 = relation30 + relation31 + relation32 + relation34 + relation35;
	assign addr4 = relation40 + relation41 + relation42 + relation43 + relation45;
	assign addr5 = relation50 + relation51 + relation52 + relation53 + relation54;

	// output character
	always @(*) begin
	out_char[5] = 0;
	out_char[4] = 0;
	out_char[3] = 0;
	out_char[2] = 0;
	out_char[1] = 0;
	out_char[0] = 0;
	out_char[addr0] = char0;
	out_char[addr1] = char1;
	out_char[addr2] = char2;
	out_char[addr3] = char3;
	out_char[addr4] = char4;
	out_char[addr5] = char5;
	end

	// output weight
	always @(*) begin
	out_w[5] = 0;
	out_w[4] = 0;
	out_w[3] = 0;
	out_w[2] = 0;
	out_w[1] = 0;
	out_w[0] = 0;
	out_w[addr0] = w0;
	out_w[addr1] = w1;
	out_w[addr2] = w2;
	out_w[addr3] = w3;
	out_w[addr4] = w4;
	out_w[addr5] = w5;
	end

	endmodule