// sqrt32.v unsigned integer sqrt 32-bits computing unsigned integer 16-bits
//   sqrt(00000000000000000000000000000100) = 0000000000000010   sqrt(4)=2
//   sqrt(00000000000000000000000001000000) = 0000000000001000   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 sqrt32(P, U);
  input [31:0] P;
  output [15:0] U;

  wire b0000, b0001, b0002, b0003, b0004, b0005, b0006, b0007, b0008,
       b0009, b0010, b0011, b0012, b0013, b0014, b0015, b0016, b0017;  
  wire x0102, x0103, x0104, x0105, x0106, x0107, x0108, x0109, x0110,
       x0111, x0112, x0113, x0114, x0115, x0116, x0117;  
  wire b0102, b0103, b0104, b0105, b0106, b0107, b0108, b0109, b0110,
       b0111, b0112, b0113, b0114, b0115, b0116, b0117, b0118;
  wire x0204, x0205, x0206, x0207, x0208, x0209, x0210, x0211, x0212,
       x0213, x0214, x0215, x0216, x0217, x0218;  
  wire b0204, b0205, b0206, b0207, b0208, b0209, b0210, b0211, b0212,
       b0213, b0214, b0215, b0216, b0217, b0218, b0219;  
  wire x0306, x0307, x0308, x0309, x0310, x0311, x0312, x0313, x0314,
       x0315, x0316, x0317, x0318, x0319;  
  wire b0306, b0307, b0308, b0309, b0310, b0311, b0312, b0313, b0314,
       b0315, b0316, b0317, b0318, b0319, b0320;  
  wire x0408, x0409, x0410, x0411, x0412, x0413, x0414, x0415, x0416,
       x0417, x0418, x0419, x0420;  
  wire b0408, b0409, b0410, b0411, b0412, b0413, b0414, b0415, b0416,
       b0417, b0418, b0419, b0420, b0421;  
  wire x0510, x0511, x0512, x0513, x0514, x0515, x0516, x0517, x0518,
       x0519, x0520, x0521;  
  wire b0510, b0511, b0512, b0513, b0514, b0515, b0516, b0517, b0518,
       b0519, b0520, b0521, b0522;  
  wire x0612, x0613, x0614, x0615, x0616, x0617, x0618, x0619, x0620,
       x0621, x0622;  
  wire b0612, b0613, b0614, b0615, b0616, b0617, b0618, b0619, b0620,
       b0621, b0622, b0623;  
  wire x0714, x0715, x0716, x0717, x0718, x0719, x0720, x0721, x0722,
       x0723;  
  wire b0714, b0715, b0716, b0717, b0718, b0719, b0720, b0721, b0722,
       b0723, b0724;  
  wire x0816, x0817, x0818, x0819, x0820, x0821, x0822, x0823, x0824;  
  wire b0816, b0817, b0818, b0819, b0820, b0821, b0822, b0823, b0824,
       b0825;  
  wire x0918, x0919, x0920, x0921, x0922, x0923, x0924, x0925;  
  wire b0918, b0919, b0920, b0921, b0922, b0923, b0924, b0925, b0926;  
  wire x1020, x1021, x1022, x1023, x1024, x1025, x1026;  
  wire b1020, b1021, b1022, b1023, b1024, b1025, b1026, b1027;  
  wire x1122, x1123, x1124, x1125, x1126, x1127;  
  wire b1122, b1123, b1124, b1125, b1126, b1127, b1128;  
  wire x1224, x1225, x1226, x1227, x1228;  
  wire b1224, b1225, b1226, b1227, b1228, b1229;  
  wire x1326, x1327, x1328, x1329;  
  wire b1326, b1327, b1328, b1329, b1330;  
  wire x1428, x1429, x1430;  
  wire b1428, b1429, b1430, b1431;  
  wire x1530, x1531;  
  wire b1530, b1531, bxx;  

  //                              x      y      b      u      d      bo
  S0 s1530(P[30],               b1531, x1530, b1530);
  S1 s1531(P[31],        b1530, b1531, x1531, bxx );
  not n1(b1531, bxx);

  S0 s1428(P[28],               b1431, x1428, b1428);
  S1 s1429(P[29],        b1428, b1431, x1429, b1429);
  Sm s1430(x1530, b1531, b1429, b1431, x1430, b1430);
  Sn s1431(x1531,        b1430,               b1431);
  
  S0 s1326(P[26],               b1330, x1326, b1326);
  S1 s1327(P[27],        b1326, b1330, x1327, b1327);
  Sm s1328(x1428, b1431, b1327, b1330, x1328, b1328);
  Sm s1329(x1429, b1531, b1328, b1330, x1329, b1329);
  Sn s1330(x1430,        b1329,               b1330);

  S0 s1224(P[24],               b1229, x1224, b1224);
  S1 s1225(P[25],        b1224, b1229, x1225, b1225);
  Sm s1226(x1326, b1330, b1225, b1229, x1226, b1226);
  Sm s1227(x1327, b1431, b1226, b1229, x1227, b1227);
  Sm s1228(x1328, b1531, b1227, b1229, x1228, b1228);
  Sn s1229(x1329,        b1228,               b1229);

  S0 s1122(P[22],               b1128, x1122, b1122);
  S1 s1123(P[23],        b1122, b1128, x1123, b1123);
  Sm s1124(x1224, b1229, b1123, b1128, x1124, b1124);
  Sm s1125(x1225, b1330, b1124, b1128, x1125, b1125);
  Sm s1126(x1226, b1431, b1125, b1128, x1126, b1126);
  Sm s1127(x1227, b1531, b1126, b1128, x1127, b1127);
  Sn s1128(x1228,        b1127,               b1128);

  S0 s1020(P[20],               b1027, x1020, b1020);
  S1 s1021(P[21],        b1020, b1027, x1021, b1021);
  Sm s1022(x1122, b1128, b1021, b1027, x1022, b1022);
  Sm s1023(x1123, b1229, b1022, b1027, x1023, b1023);
  Sm s1024(x1124, b1330, b1023, b1027, x1024, b1024);
  Sm s1025(x1125, b1431, b1024, b1027, x1025, b1025);
  Sm s1026(x1126, b1531, b1025, b1027, x1026, b1026);
  Sn s1027(x1127,        b1026,               b1027);

  S0 s0918(P[18],               b0926, x0918, b0918);
  S1 s0919(P[19],        b0918, b0926, x0919, b0919);
  Sm s0920(x1020, b1027, b0919, b0926, x0920, b0920);
  Sm s0921(x1021, b1128, b0920, b0926, x0921, b0921);
  Sm s0922(x1022, b1229, b0921, b0926, x0922, b0922);
  Sm s0923(x1023, b1330, b0922, b0926, x0923, b0923);
  Sm s0924(x1024, b1431, b0923, b0926, x0924, b0924);
  Sm s0925(x1025, b1531, b0924, b0926, x0925, b0925);
  Sn s0926(x1026,        b0925,               b0926);

  S0 s0816(P[16],               b0825, x0816, b0816);
  S1 s0817(P[17],        b0816, b0825, x0817, b0817);
  Sm s0818(x0918, b0926, b0817, b0825, x0818, b0818);
  Sm s0819(x0919, b1027, b0818, b0825, x0819, b0819);
  Sm s0820(x0920, b1128, b0819, b0825, x0820, b0820);
  Sm s0821(x0921, b1229, b0820, b0825, x0821, b0821);
  Sm s0822(x0922, b1330, b0821, b0825, x0822, b0822);
  Sm s0823(x0923, b1431, b0822, b0825, x0823, b0823);
  Sm s0824(x0924, b1531, b0823, b0825, x0824, b0824);
  Sn s0825(x0925,        b0824,               b0825);

  S0 s0714(P[14],               b0724, x0714, b0714);
  S1 s0715(P[15],        b0714, b0724, x0715, b0715);
  Sm s0716(x0816, b0825, b0715, b0724, x0716, b0716);
  Sm s0717(x0817, b0926, b0716, b0724, x0717, b0717);
  Sm s0718(x0818, b1027, b0717, b0724, x0718, b0718);
  Sm s0719(x0819, b1128, b0718, b0724, x0719, b0719);
  Sm s0720(x0820, b1229, b0719, b0724, x0720, b0720);
  Sm s0721(x0821, b1330, b0720, b0724, x0721, b0721);
  Sm s0722(x0822, b1431, b0721, b0724, x0722, b0722);
  Sm s0723(x0823, b1531, b0722, b0724, x0723, b0723);
  Sn s0724(x0824,        b0723,               b0724);
 
  S0 s0612(P[12],               b0623, x0612, b0612);
  S1 s0613(P[13],        b0612, b0623, x0613, b0613);
  Sm s0614(x0714, b0724, b0613, b0623, x0614, b0614);
  Sm s0615(x0715, b0825, b0614, b0623, x0615, b0615);
  Sm s0616(x0716, b0926, b0615, b0623, x0616, b0616);
  Sm s0617(x0717, b1027, b0616, b0623, x0617, b0617);
  Sm s0618(x0718, b1128, b0617, b0623, x0618, b0618);
  Sm s0619(x0719, b1229, b0618, b0623, x0619, b0619);
  Sm s0620(x0720, b1330, b0619, b0623, x0620, b0620);
  Sm s0621(x0721, b1431, b0620, b0623, x0621, b0621);
  Sm s0622(x0722, b1531, b0621, b0623, x0622, b0622);
  Sn s0623(x0723,        b0622,               b0623);
  
  S0 s0510(P[10],               b0522, x0510, b0510);
  S1 s0511(P[11],        b0510, b0522, x0511, b0511);
  Sm s0512(x0612, b0622, b0511, b0522, x0512, b0512);
  Sm s0513(x0613, b0723, b0512, b0522, x0513, b0513);
  Sm s0514(x0614, b0825, b0513, b0522, x0514, b0514);
  Sm s0515(x0615, b0926, b0514, b0522, x0515, b0515);
  Sm s0516(x0616, b1027, b0515, b0522, x0516, b0516);
  Sm s0517(x0617, b1128, b0516, b0522, x0517, b0517);
  Sm s0518(x0618, b1229, b0517, b0522, x0518, b0518);
  Sm s0519(x0619, b1330, b0518, b0522, x0519, b0519);
  Sm s0520(x0620, b1431, b0519, b0522, x0520, b0520);
  Sm s0521(x0621, b1531, b0520, b0522, x0521, b0521);
  Sn s0522(x0622,        b0521,               b0522);

  S0 s0408(P[8],                b0421, x0408, b0408);
  S1 s0409(P[9],         b0408, b0421, x0409, b0409);
  Sm s0410(x0510, b0522, b0409, b0421, x0410, b0410);
  Sm s0411(x0511, b0623, b0410, b0421, x0411, b0411);
  Sm s0412(x0512, b0724, b0411, b0421, x0412, b0412);
  Sm s0413(x0513, b0825, b0412, b0421, x0413, b0413);
  Sm s0414(x0514, b0926, b0413, b0421, x0414, b0414);
  Sm s0415(x0515, b1027, b0414, b0421, x0415, b0415);
  Sm s0416(x0516, b1128, b0415, b0421, x0416, b0416);
  Sm s0417(x0517, b1229, b0416, b0421, x0417, b0417);
  Sm s0418(x0518, b1330, b0417, b0421, x0418, b0418);
  Sm s0419(x0519, b1431, b0418, b0421, x0419, b0419);
  Sm s0420(x0520, b1531, b0419, b0421, x0420, b0420);
  Sn s0421(x0521,        b0420,               b0421);

  S0 s0306(P[6],                b0320, x0306, b0306);
  S1 s0307(P[7],         b0306, b0320, x0307, b0307);
  Sm s0308(x0408, b0421, b0307, b0320, x0308, b0308);
  Sm s0309(x0409, b0522, b0308, b0320, x0309, b0309);
  Sm s0310(x0410, b0623, b0309, b0320, x0310, b0310);
  Sm s0311(x0411, b0724, b0310, b0320, x0311, b0311);
  Sm s0312(x0412, b0825, b0311, b0320, x0312, b0312);
  Sm s0313(x0413, b0926, b0312, b0320, x0313, b0313);
  Sm s0314(x0414, b1027, b0313, b0320, x0314, b0314);
  Sm s0315(x0415, b1128, b0314, b0320, x0315, b0315);
  Sm s0316(x0416, b1229, b0315, b0320, x0316, b0316);
  Sm s0317(x0417, b1330, b0316, b0320, x0317, b0317);
  Sm s0318(x0418, b1431, b0317, b0320, x0318, b0318);
  Sm s0319(x0419, b1531, b0318, b0320, x0319, b0319);
  Sn s0320(x0420,        b0319,               b0320);

  S0 s0204(P[4],                b0219, x0204, b0204);
  S1 s0205(P[5],         b0204, b0219, x0205, b0205);
  Sm s0206(x0306, b0320, b0205, b0219, x0206, b0206);
  Sm s0207(x0307, b0421, b0206, b0219, x0207, b0207);
  Sm s0208(x0308, b0522, b0207, b0219, x0208, b0208);
  Sm s0209(x0309, b0623, b0208, b0219, x0209, b0209);
  Sm s0210(x0310, b0724, b0209, b0219, x0210, b0210);
  Sm s0211(x0311, b0825, b0210, b0219, x0211, b0211);
  Sm s0212(x0312, b0926, b0211, b0219, x0212, b0212);
  Sm s0213(x0313, b1027, b0212, b0219, x0213, b0213);
  Sm s0214(x0314, b1128, b0213, b0219, x0214, b0214);
  Sm s0215(x0315, b1229, b0214, b0219, x0215, b0215);
  Sm s0216(x0316, b1330, b0215, b0219, x0216, b0216);
  Sm s0217(x0317, b1431, b0216, b0219, x0217, b0217);
  Sm s0218(x0318, b1531, b0217, b0219, x0218, b0218);
  Sn s0219(x0319,        b0218,               b0219);

  S0 s0102(P[2],                b0118, x0102, b0102);
  S1 s0103(P[3],         b0102, b0118, x0103, b0103);
  Sm s0104(x0204, b0219, b0103, b0118, x0104, b0104);
  Sm s0105(x0205, b0320, b0104, b0118, x0105, b0105);
  Sm s0106(x0206, b0421, b0105, b0118, x0106, b0106);
  Sm s0107(x0207, b0522, b0106, b0118, x0107, b0107);
  Sm s0108(x0208, b0623, b0107, b0118, x0108, b0108);
  Sm s0109(x0209, b0724, b0108, b0118, x0109, b0109);
  Sm s0110(x0210, b0825, b0109, b0118, x0110, b0110);
  Sm s0111(x0211, b0926, b0110, b0118, x0111, b0111);
  Sm s0112(x0212, b1027, b0111, b0118, x0112, b0112);
  Sm s0113(x0213, b1128, b0112, b0118, x0113, b0113);
  Sm s0114(x0214, b1229, b0113, b0118, x0114, b0114);
  Sm s0115(x0215, b1330, b0114, b0118, x0115, b0115);
  Sm s0116(x0216, b1431, b0115, b0118, x0116, b0116);
  Sm s0117(x0217, b1531, b0116, b0118, x0117, b0117);
  Sn s0118(x0218,        b0117,               b0118);

  S0b s0000(P[0],                              b0000);
  S1b s0001(P[1],         b0000,               b0001);
  Sb s0002(x0102, b0118, b0001,               b0002);
  Sb s0003(x0103, b0219, b0002,               b0003);
  Sb s0004(x0104, b0320, b0003,               b0004);
  Sb s0005(x0105, b0421, b0004,               b0005);
  Sb s0006(x0106, b0522, b0005,               b0006);
  Sb s0007(x0107, b0623, b0006,               b0007);
  Sb s0008(x0108, b0724, b0007,               b0008);
  Sb s0009(x0109, b0825, b0008,               b0009);
  Sb s0010(x0110, b0926, b0009,               b0010);
  Sb s0011(x0111, b1027, b0010,               b0011);
  Sb s0012(x0112, b1128, b0011,               b0012);
  Sb s0013(x0113, b1229, b0012,               b0013);
  Sb s0014(x0114, b1330, b0013,               b0014);
  Sb s0015(x0115, b1431, b0014,               b0015);
  Sb s0016(x0116, b1531, b0015,               b0016);
  Sn s0017(x0117,        b0016,               b0017);

  buf b0 (U[0],  b0017); // set output bits
  buf b1 (U[1],  b0118);
  buf b2 (U[2],  b0219);
  buf b3 (U[3],  b0320);
  buf b4 (U[4],  b0421);
  buf b5 (U[5],  b0522);
  buf b6 (U[6],  b0623);
  buf b7 (U[7],  b0724);
  buf b8 (U[8],  b0825);
  buf b9 (U[9],  b0926);
  buf b10(U[10], b1027);
  buf b11(U[11], b1128);
  buf b12(U[12], b1229);
  buf b13(U[13], b1330);
  buf b14(U[14], b1431);
  buf b15(U[15], b1531);        
endmodule  //  sqrt32


module tsqrt32;  // test driver
  reg [31:0] P;
  wire [15:0] U;
  reg [7:0] temp;
  integer i;
  
  // test of sqrt32
  sqrt32 s1(P, U);    // instantiate module
  initial
    begin  // test cases
      for(i=0; i<256; i=i+1)
        begin
          temp = i;
          P = {temp,temp,temp,temp};
          #257 $display("sqrt( %b )= %b", P, U);
        end
    end
endmodule  //  tsqrt32