001 #ifndef BBC_128 
002 #define BBC_128
003 union CU128 {
004   U32 u32[4];
005   U64 _u64[2];
006 };
007 CU128 *U128Copy(CU128 *a,CU128 *b) {
008   a->_u64[0]=b->_u64[0];
009   a->_u64[1]=b->_u64[1];
010   return a;
011 }
012 U8 *U128ToStr(CU128 *big) {
013   return MStrPrint("%016x%016x",big->_u64[1],big->_u64[0]);
014 }
015 I64 CompareU128(CU128 *a,CU128 *b) {
016   if(a->_u64[1]!=b->_u64[1]) {
017     if(a->_u64[1]>b->_u64[1])
018       return 1;
019     if(a->_u64[1]<b->_u64[1])
020       return -1;
021     return 0;
022   }
023   if(a->_u64[0]>b->_u64[0])
024     return 1;
025   if(a->_u64[0]<b->_u64[0])
026     return -1;
027   return 0;  
028 };
029 CU128 *ToU128(CU128 *res,I64 v) {
030   res->_u64[1]=0;
031   res->_u64[0]=v; 
032   return res;
033 }
034 CU128 *AddU128(CU128 *res,CU128 *a,CU128 *b) {
035   I64 carry=0,part;
036   CU128 dumb;
037   if(res==a)
038     a=U128Copy(&dumb,a);
039   else if(res==b)
040     b=U128Copy(&dumb,b);
041 
042   for(part=0;part!=4;part++)  {
043     carry=a->u32[part]+b->u32[part]+carry;
044     res->u32[part]=carry;
045     carry>>=32;
046   }
047   return res; 
048 }
049 CU128 *NegativeU128(CU128 *res,CU128 *r) {
050   CU128 o;
051   res->_u64[0]=~r->_u64[0];
052   res->_u64[1]=~r->_u64[1];
053   ToU128(&o,1);
054   AddU128(res,res,&o);
055   return res;
056 }
057 CU128 *SubU128(CU128 *res,CU128 *a,CU128 *b) {
058   CU128 dumb;
059   return AddU128(res,a,NegativeU128(&dumb,b)); 
060 }
061 CU128 *MulU128(CU128 *res,CU128 *a,CU128 *b) {
062   U32 carry[8*2];
063   U64 da,db,result;
064   CU128 dumb;
065   if(res==a)
066     a=U128Copy(&dumb,a);
067   else if(res==b)
068     b=U128Copy(&dumb,b);
069 
070   MemSet(res,0,16);
071   
072   for(db=0;db!=4;db++) {
073     MemSetU32(carry,0,4);
074     for(da=0;da!=4;da++) {
075       result=carry[db+da]+a->u32[da]*b->u32[db];
076       carry[db+da]=result;
077       carry[db+da+1]=result>>32;
078     }
079     AddU128(res,res,carry);
080   }
081   return res;
082 }
083 CU128 *DivU128(CU128 *res,CU128 *a,CU128 *b,CU128 *mod=NULL) {
084   CU128 tmp,final,one,tmp2,good;
085   I64 shift=0;
086   U128Copy(&tmp,a);
087   MemSet(&final,0,16);
088   ToU128(&one,1);
089 again:;
090   shift=0;
091   U128Copy(&tmp2,b);
092   while(shift<62&&CompareU128(&tmp,&tmp2)>=1) {
093     ++shift;
094     U128Copy(&good,&tmp2);
095     AddU128(&tmp2,&tmp2,&tmp2);
096   }
097   if(shift) {
098     ToU128(&tmp2,1<<(shift-1));
099     AddU128(&final,&final,&tmp2);
100     SubU128(&tmp,&tmp,&good);
101     goto again;
102   }
103   while(CompareU128(&tmp,b)==1) {
104     SubU128(&tmp,&tmp,b);
105     AddU128(&final,&final,&one);
106   }
107   if(mod) U128Copy(mod,&tmp);
108   U128Copy(res,&final);
109   return res;
110 }
111 CU128 *Str2U128(CU128 *u128,U8 *str) {
112   U8 dumb2[STR_LEN];
113   StrCpy(dumb2,str);
114   str=dumb2;
115   U8 dumb[STR_LEN];
116   I64 len=StrLen(str);
117   I64 byte=0;
118   u128->_u64[0]=0;
119   u128->_u64[1]=0;
120   while(len>0) {
121     if(len>=2) {
122       len-=2;
123       dumb[0](U16)=str[len](U16);
124       str[len]=0;
125       dumb[2]=0;
126     } else {
127       dumb[0]=str[--len];
128       dumb[1]=0;
129     }
130     u128(U8*)[byte++]=Str2I64(dumb,16); 
131     if(byte>=16)
132       break;
133   }
134   return u128;
135 }
136 
137 #if __CMD_LINE__
138 CU128 a,b,r,r2;
139 ToU128(&a,I64_MAX); 
140 ToU128(&b,256);
141 "NEG%s\n",U128ToStr(NegativeU128(&r,&a));
142 "+%s\n",U128ToStr(AddU128(&r,&a,&b));
143 "-%s\n",U128ToStr(SubU128(&r2,&r,&a));
144 "-%s\n",U128ToStr(SubU128(&r2,&r,&b));
145 "*%s\n",U128ToStr(MulU128(&r,&a,&b));
146 ToU128(&a,I64_MAX*2);
147 ToU128(&b,75);
148 "/%s,%x\n",U128ToStr(DivU128(&r,&a,&b,&r2)),I64_MAX/75;
149 "%s,%x\n",U128ToStr(&r2),I64_MAX%75;
150 "%s\n",U128ToStr(Str2U128(&r,"0xb83fe991ca66800489155dcd69e8426ba2779453994ac90ed284034da565ecf"));
151 #endif
152 #endif