// sqrt8m.v     unsigned integer sqrt 8-bits computing unsigned integer 4-bits
//             sqrt(00000100) = 0010   sqrt(4)=2
//             sqrt(01000000) = 1000   sqrt(64)=8

`timescale 1ns/1ns

module Sm(x, y, b, u, d, bo);  // subtractor multiplexor 
  input  x;
  input  y;
  input  b;
  input  u;
  output d;
  output bo;

  wire t011, t111, t010, t001, t100, td;
  wire x_, y_, b_, u_, if_td, if_x;

  // circuits of Sm
  not notx(x_, x);
  not noty(y_, y);
  not notb(b_, b);
  and a011(t011, x_, y,  b );
  and a111(t111, x,  y,  b );
  and a010(t010, x_, y,  b_);
  and a001(t001, x_, y_, b );
  and a100(t100, x,  y_, b_);
  or  #1 or1(bo, t011, t111, t010, t001);
  or  or2(td, t100, t001, t010, t111);
  not notu(u_, u);  // four gate mux
  and atd(if_td, td, u); 
  and ax (if_x,   x, u_);
  or  #1 or3(d, if_td, if_x);
endmodule  // Sm


module Sb(x, y, b, bo);  // subtractor multiplexor stage b 
  input  x;
  input  y;
  input  b;
  output bo;

  wire t011, t111, t010, t001;
  wire x_, y_, b_;

  // circuits of Sb
  not n01(x_, x);
  not n02(y_, y);
  not n03(b_, b);
  and a011(t011, x_, y,  b);
  and a111(t111, x,  y,  b);
  and a010(t010, x_, y,  b_);
  and a001(t001, x_, y_,  b);
  or #1 bor(bo, t011, t111, t010, t001);
endmodule  // Sb

module S1(x, b, u, d, bo);  // subtractor multiplexor stage 1
  input  x;
  input  b;
  input  u;
  output d;
  output bo;

  wire t100, t001, td;
  wire x_, b_, u_, if_td, if_x;

  // circuits of S1
  not not1(x_, x);
  not not2(b_, b);
  and a011(t001, x_,  b);
  and a100(t100, x,   b_);
  buf #1 buf1(bo, t001);
  or or1(td, t100, t001);
  not notu(u_, u);  // four gate mux
  and atd(if_td, td, u); 
  and ax (if_x,   x, u_);
  or  #1 or3(d, if_td, if_x);
endmodule  //  S1

module S0(x, u, d, bo);    // subtractor multiplexor stage 0
  input  x;
  input  u;
  output d;
  output bo;

  wire u_, if_bo, if_x;

  // circuits of S0
  not #1 n1(bo, x);
  not notu(u_, u);  // four gate mux
  and atd(if_bo, bo, u); 
  and ax (if_x,   x, u_);
  or  #1 or3(d, if_bo, if_x);
endmodule  //  S0

module Sn(x, b, bo); // subtractor multiplexor stage n 
  input  x;
  input  b;
  output bo;

  wire x_;

  // circuits of Sn, complemented
  not  n00(x_, x);
  nand #1 n01(bo, x_, b);
endmodule  //  Sn

module S0b(x, bo);   // subtractor multiplexor stage 0b
  input  x;
  output bo;

  // circuits of S0b
  not #1 n0(bo, x);
endmodule  //  S0b

module S1b(x, b, bo);     // subtractor multiplexor stage 1b
  input  x;
  input  b;
  output bo;

  wire x_;

  // circuits of S1b
  not n00(x_, x);
  and #1 n01(bo, x_, b);
endmodule  //  S1b


module psqrt(P, U);
  input [7:0] P;
  output [3:0] U;

  wire b00, b01, b02, b03, b04, b05;  
  wire x12, x13, x14, x15;  
  wire b12, b13, b14, b15, b16;  
  wire x24, x25, x26;  
  wire b24, b25, b26, b27;  
  wire x36, x37, bxx;  
  wire b36, b37;  

  // circuits of psqrt
  //       x     y    b    u    d    bo
  S0  s36(P[6],           b37, x36, b36);
  S1  s37(P[7],      b36, b37, x37, bxx);
  not t37(b37,  bxx);

  S0  s24(P[4],           b27, x24, b24);
  S1  s25(P[5],      b24, b27, x25, b25);
  Sm  s26(x36 , b37, b25, b27, x26, b26);
  Sn  s27(x37 ,      b26,           b27);

  S0  s12(P[2],           b16, x12, b12);
  S1  s13(P[3],      b12, b16, x13, b13);
  Sm  s14(x24 , b27, b13, b16, x14, b14);
  Sm  s15(x25 , b37, b14, b16, x15, b15);
  Sn  s16(x26 ,      b15,           b16);

  S0b s00(P[0],                     b00);
  S1b s01(P[1],      b00,           b01);
  Sb  s02(x12 , b16, b01,           b02);
  Sb  s03(x13 , b27, b02,           b03);
  Sb  s04(x14 , b37, b03,           b04);
  Sn  s05(x15 ,      b04,           b05);
  buf buf1(U[0], b05);
  buf buf2(U[1], b16);
  buf buf3(U[2], b27);
  buf buf4(U[3], b37);

endmodule  // psqrt

module sqrt8m;  // test driver
  reg [7:0] P;
  wire [3:0] U;
  integer i;
  
  // test of sqrt8m
  psqrt s1(P, U);    // instantiate module
  initial
    begin  // test cases
      for(i=0; i<256; i=i+1)
        begin
          P = i;
          #40 $display("sqrt( %b )= %b", P, U);
        end
    end
endmodule  //  sqrt8m