1 // ash().
2 
3 // General includes.
4 #include "base/cl_sysdep.h"
5 
6 // Specification.
7 #include "cln/integer.h"
8 
9 
10 // Implementation.
11 
12 #include "integer/cl_I.h"
13 #include "base/digitseq/cl_DS.h"
14 
15 namespace cln {
16 
ash(const cl_I & x,const cl_I & y)17 const cl_I ash (const cl_I& x, const cl_I& y)
18 {
19     // Methode:
20     // x = 0 -> 0 als Ergebnis
21     // y = 0 -> x als Ergebnis
22     // y > 0 -> y = intDsize*k + i, j=k+(1 falls i>0, 0 falls i=0).
23     //          j Wörter mehr reservieren, k Nullwörter, dann übertragen,
24     //          bei i>0: um i Bits links schieben (i=1 geht einfacher).
25     // y < 0 -> y <= - intDsize * (Länge(A0) in Digits) -> Ergebnis = 0 oder -1.
26     //          Sonst: -y = intDsize*k + i mit k<Länge(A0).
27     //                  Übertrage die (Länge(A0)-k) MSDigits,
28     //                  falls i>0: schiebe sie um i Bits nach rechts (i=1 geht einfacher).
29 	if (zerop(x))
30 		return 0;		// x=0 -> 0 als Ergebnis
31 	if (zerop(y))
32 		return x;		// y=0 -> x als Ergebnis
33 	CL_ALLOCA_STACK;
34 	if (!minusp(y)) {
35 		// y>=0
36 		var uintL i; // i = y mod intDsize, >=0, <intDsize
37 		var uintC k; // k = y div intDsize, >=0, <2^intCsize
38 		if (bignump(y)) {
39 			#if (log2_intDsize+intCsize <= cl_value_len-1)
40 			// y >= 2^(cl_value_len-1) >= intDsize*2^intCsize
41 			throw ash_exception(y);
42 			#else
43 			// y >= 2^(cl_value_len-1)
44 			// usable only if y < intDsize*2^intCsize
45 			var cl_heap_bignum* bn = TheBignum(y);
46 			var uintC len = bn->length;
47 			if (len > ceiling(log2_intDsize+intCsize+1,intDsize))
48 				throw ash_exception(y);
49 			// bn_minlength <= len <= ceiling(log2_intDsize+intCsize+1,intDsize).
50 			if (bn_minlength == ceiling(log2_intDsize+intCsize+1,intDsize)
51 			    || len == ceiling(log2_intDsize+intCsize+1,intDsize))
52 				if (mspref(arrayMSDptr(bn->data,len),0) >= (uintD)bit((log2_intDsize+intCsize)%intDsize))
53 					throw ash_exception(y);
54 			#if (log2_intDsize+intCsize > intDsize)
55 			#define IF_LENGTH(i)  \
56 			  if (bn_minlength <= i && i <= ceiling(log2_intDsize+intCsize+1,intDsize) && (i == ceiling(log2_intDsize+intCsize+1,intDsize) || len == i))
57 			IF_LENGTH(1)
58 				k = 0;
59 			else IF_LENGTH(2)
60 				k = get_uint1D_Dptr(arrayLSDptr(bn->data,2) lspop 1);
61 			else IF_LENGTH(3)
62 				k = get_uint2D_Dptr(arrayLSDptr(bn->data,3) lspop 1);
63 			else IF_LENGTH(4)
64 				k = get_uint3D_Dptr(arrayLSDptr(bn->data,4) lspop 1);
65 			else IF_LENGTH(5)
66 				k = get_uint4D_Dptr(arrayLSDptr(bn->data,5) lspop 1);
67 			else
68 				throw runtime_exception();
69 			#undef IF_LENGTH
70 			k = k << (intDsize-log2_intDsize);
71 			#else
72 			// log2_intDsize+intCsize <= intDsize,
73 			// implies len==1 or len==2 && lspref(arrayLSDptr(bn->data,len),1) == 0.
74 			k = 0;
75 			#endif
76 			k |= lspref(arrayLSDptr(bn->data,len),0) >> log2_intDsize;
77 			i = lspref(arrayLSDptr(bn->data,len),0) % intDsize;
78 			#endif
79 		} else {
80 			var uintV y_ = FN_to_V(y); // Wert von y, >=0, <intDsize*2^intCsize
81 			i = y_%intDsize;
82 			k = floor(y_,intDsize);
83 		}
84 		var uintD* LSDptr;
85 		var uintC len;
86 		var const uintD* x_LSDptr;
87 		I_to_NDS_nocopy(x, ,len=,x_LSDptr=,false,); // DS zu x bilden.
88 		if (k >= (uintC)(~len)) // kann len+k+1 Überlauf geben?
89 			{ throw ash_exception(y); } // ja -> Fehler
90 		num_stack_alloc_1(len+k,,LSDptr=);
91 		LSDptr = clear_loop_lsp(LSDptr,k); // k Nulldigits
92 		var uintD* MSDptr = copy_loop_lsp(x_LSDptr,LSDptr,len);
93 		// Nun ist MSDptr/len/LSDptr die DS zu x.
94 		// Oberhalb von ihr liegen k Nulldigits, unterhalb ist 1 Digit Platz.
95 		// MSDptr/len+k/.. ist jetzt die Gesamt-DS.
96 		// Noch um i Bits nach links schieben:
97 		if (!(i==0)) // Bei i>0
98 		  { // noch ein weiteres Digit dazunehmen (Vorzeichen)
99 		    {var uintD sign = sign_of_sintD(mspref(MSDptr,0));
100 		     lsprefnext(MSDptr) = sign;
101 		     len++;
102 		    }
103 		    // Schiebeschleife: die unteren len Digits um i Bits schieben
104 		    if (i==1)
105 		      { shift1left_loop_lsp(LSDptr,len); }
106 		    else
107 		      { shiftleft_loop_lsp(LSDptr,len,i,0); }
108 		  }
109 		return DS_to_I(MSDptr,len+k);
110 	} else {
111 		// y<0
112 		var uintL i; // i = (-y) mod intDsize, >=0, <intDsize
113 		var uintC k; // k = (-y) div intDsize, >=0, <2^intCsize
114 		if (bignump(y)) {
115 			#if (log2_intDsize+intCsize <= cl_value_len-1)
116 			// -y-1 >= 2^(cl_value_len-1) >= intDsize*2^intCsize
117 			goto sign;
118 			#else
119 			// -y-1 >= 2^(cl_value_len-1)
120 			// usable only if -y-1 < intDsize*2^intCsize
121 			// We write -y-1 = lognot(y) = k*intDsize+i and then add 1.
122 			var cl_heap_bignum* bn = TheBignum(y);
123 			var uintC len = bn->length;
124 			if (len > ceiling(log2_intDsize+intCsize+1,intDsize))
125 				goto sign;
126 			// bn_minlength <= len <= ceiling(log2_intDsize+intCsize+1,intDsize).
127 			if (bn_minlength == ceiling(log2_intDsize+intCsize+1,intDsize)
128 			    || len == ceiling(log2_intDsize+intCsize+1,intDsize))
129 				if (mspref(arrayMSDptr(bn->data,len),0) < (uintD)(-bit((log2_intDsize+intCsize)%intDsize)))
130 					goto sign;
131 			#if (log2_intDsize+intCsize > intDsize)
132 			#define IF_LENGTH(i)  \
133 			  if (bn_minlength <= i && i <= ceiling(log2_intDsize+intCsize+1,intDsize) && (i == ceiling(log2_intDsize+intCsize+1,intDsize) || len == i))
134 			IF_LENGTH(1)
135 				k = 0;
136 			else IF_LENGTH(2)
137 				k = ~get_sint1D_Dptr(arrayLSDptr(bn->data,2) lspop 1);
138 			else IF_LENGTH(3)
139 				k = ~get_sint2D_Dptr(arrayLSDptr(bn->data,3) lspop 1);
140 			else IF_LENGTH(4)
141 				k = ~get_sint3D_Dptr(arrayLSDptr(bn->data,4) lspop 1);
142 			else IF_LENGTH(5)
143 				k = ~get_sint4D_Dptr(arrayLSDptr(bn->data,5) lspop 1);
144 			else
145 				throw runtime_exception();
146 			#undef IF_LENGTH
147 			k = k << (intDsize-log2_intDsize);
148 			#else
149 			// log2_intDsize+intCsize <= intDsize,
150 			// implies len==1 or len==2 && lspref(arrayLSDptr(bn->data,len),1) == ~0.
151 			k = 0;
152 			#endif
153 			k |= (uintD)(~lspref(arrayLSDptr(bn->data,len),0)) >> log2_intDsize;
154 			i = (uintD)(-lspref(arrayLSDptr(bn->data,len),0)) % intDsize;
155 			if (i == 0)
156 				if (++k == 0)
157 					goto sign;
158 			#endif
159 		} else {
160 			var uintV y_ = -FN_to_V(y); // Wert von -y, >0, <intDsize*2^intCsize
161 			i = y_%intDsize;
162 			k = floor(y_,intDsize);
163 		}
164 		// DS zu x bilden:
165 		var uintD* MSDptr;
166 		var uintC len;
167 		I_to_NDS(x, MSDptr=,len=,); // DS zu x bilden.
168 		if (k>=len) goto sign; // -y >= intDsize*len -> Vorzeichen von x zurück
169 		len -= k; // rechte k Digits einfach streichen
170 		// Noch ist len>0. Um i Bits nach rechts schieben:
171 		if (!(i==0)) // Bei i>0:
172 		  { // Schiebe len Digits ab MSDptr um i Bits nach rechts:
173 		    if (i==1)
174 		      { shift1right_loop_msp(MSDptr,len,sign_of_sintD(mspref(MSDptr,0))); }
175 		      else
176 		      { shiftrightsigned_loop_msp(MSDptr,len,i); }
177 		  }
178 		return DS_to_I(MSDptr,len);
179 	}
180 sign:	// Ergebnis ist 0, falls x>=0, und -1, falls x<0:
181 	return (minusp(x) ? cl_I(-1) : cl_I(0));
182 }
183 
184 }  // namespace cln
185