Line data Source code
1 : /*
2 : * Copyright 2015 Advanced Micro Devices, Inc.
3 : *
4 : * Permission is hereby granted, free of charge, to any person obtaining a
5 : * copy of this software and associated documentation files (the "Software"),
6 : * to deal in the Software without restriction, including without limitation
7 : * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 : * and/or sell copies of the Software, and to permit persons to whom the
9 : * Software is furnished to do so, subject to the following conditions:
10 : *
11 : * The above copyright notice and this permission notice shall be included in
12 : * all copies or substantial portions of the Software.
13 : *
14 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
17 : * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 : * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 : * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 : * OTHER DEALINGS IN THE SOFTWARE.
21 : *
22 : */
23 : #include <asm/div64.h>
24 :
25 : #define SHIFT_AMOUNT 16 /* We multiply all original integers with 2^SHIFT_AMOUNT to get the fInt representation */
26 :
27 : #define PRECISION 5 /* Change this value to change the number of decimal places in the final output - 5 is a good default */
28 :
29 : #define SHIFTED_2 (2 << SHIFT_AMOUNT)
30 : #define MAX (1 << (SHIFT_AMOUNT - 1)) - 1 /* 32767 - Might change in the future */
31 :
32 : /* -------------------------------------------------------------------------------
33 : * NEW TYPE - fINT
34 : * -------------------------------------------------------------------------------
35 : * A variable of type fInt can be accessed in 3 ways using the dot (.) operator
36 : * fInt A;
37 : * A.full => The full number as it is. Generally not easy to read
38 : * A.partial.real => Only the integer portion
39 : * A.partial.decimal => Only the fractional portion
40 : */
41 : typedef union _fInt {
42 : int full;
43 : struct _partial {
44 : unsigned int decimal: SHIFT_AMOUNT; /*Needs to always be unsigned*/
45 : int real: 32 - SHIFT_AMOUNT;
46 : } partial;
47 : } fInt;
48 :
49 : /* -------------------------------------------------------------------------------
50 : * Function Declarations
51 : * -------------------------------------------------------------------------------
52 : */
53 : static fInt ConvertToFraction(int); /* Use this to convert an INT to a FINT */
54 : static fInt Convert_ULONG_ToFraction(uint32_t); /* Use this to convert an uint32_t to a FINT */
55 : static fInt GetScaledFraction(int, int); /* Use this to convert an INT to a FINT after scaling it by a factor */
56 : static int ConvertBackToInteger(fInt); /* Convert a FINT back to an INT that is scaled by 1000 (i.e. last 3 digits are the decimal digits) */
57 :
58 : static fInt fNegate(fInt); /* Returns -1 * input fInt value */
59 : static fInt fAdd (fInt, fInt); /* Returns the sum of two fInt numbers */
60 : static fInt fSubtract (fInt A, fInt B); /* Returns A-B - Sometimes easier than Adding negative numbers */
61 : static fInt fMultiply (fInt, fInt); /* Returns the product of two fInt numbers */
62 : static fInt fDivide (fInt A, fInt B); /* Returns A/B */
63 : static fInt fGetSquare(fInt); /* Returns the square of a fInt number */
64 : static fInt fSqrt(fInt); /* Returns the Square Root of a fInt number */
65 :
66 : static int uAbs(int); /* Returns the Absolute value of the Int */
67 : static int uPow(int base, int exponent); /* Returns base^exponent an INT */
68 :
69 : static void SolveQuadracticEqn(fInt, fInt, fInt, fInt[]); /* Returns the 2 roots via the array */
70 : static bool Equal(fInt, fInt); /* Returns true if two fInts are equal to each other */
71 : static bool GreaterThan(fInt A, fInt B); /* Returns true if A > B */
72 :
73 : static fInt fExponential(fInt exponent); /* Can be used to calculate e^exponent */
74 : static fInt fNaturalLog(fInt value); /* Can be used to calculate ln(value) */
75 :
76 : /* Fuse decoding functions
77 : * -------------------------------------------------------------------------------------
78 : */
79 : static fInt fDecodeLinearFuse(uint32_t fuse_value, fInt f_min, fInt f_range, uint32_t bitlength);
80 : static fInt fDecodeLogisticFuse(uint32_t fuse_value, fInt f_average, fInt f_range, uint32_t bitlength);
81 : static fInt fDecodeLeakageID (uint32_t leakageID_fuse, fInt ln_max_div_min, fInt f_min, uint32_t bitlength);
82 :
83 : /* Internal Support Functions - Use these ONLY for testing or adding to internal functions
84 : * -------------------------------------------------------------------------------------
85 : * Some of the following functions take two INTs as their input - This is unsafe for a variety of reasons.
86 : */
87 : static fInt Divide (int, int); /* Divide two INTs and return result as FINT */
88 : static fInt fNegate(fInt);
89 :
90 : static int uGetScaledDecimal (fInt); /* Internal function */
91 : static int GetReal (fInt A); /* Internal function */
92 :
93 : /* -------------------------------------------------------------------------------------
94 : * TROUBLESHOOTING INFORMATION
95 : * -------------------------------------------------------------------------------------
96 : * 1) ConvertToFraction - InputOutOfRangeException: Only accepts numbers smaller than MAX (default: 32767)
97 : * 2) fAdd - OutputOutOfRangeException: Output bigger than MAX (default: 32767)
98 : * 3) fMultiply - OutputOutOfRangeException:
99 : * 4) fGetSquare - OutputOutOfRangeException:
100 : * 5) fDivide - DivideByZeroException
101 : * 6) fSqrt - NegativeSquareRootException: Input cannot be a negative number
102 : */
103 :
104 : /* -------------------------------------------------------------------------------------
105 : * START OF CODE
106 : * -------------------------------------------------------------------------------------
107 : */
108 0 : static fInt fExponential(fInt exponent) /*Can be used to calculate e^exponent*/
109 : {
110 : uint32_t i;
111 0 : bool bNegated = false;
112 :
113 0 : fInt fPositiveOne = ConvertToFraction(1);
114 0 : fInt fZERO = ConvertToFraction(0);
115 :
116 0 : fInt lower_bound = Divide(78, 10000);
117 0 : fInt solution = fPositiveOne; /*Starting off with baseline of 1 */
118 : fInt error_term;
119 :
120 : static const uint32_t k_array[11] = {55452, 27726, 13863, 6931, 4055, 2231, 1178, 606, 308, 155, 78};
121 : static const uint32_t expk_array[11] = {2560000, 160000, 40000, 20000, 15000, 12500, 11250, 10625, 10313, 10156, 10078};
122 :
123 0 : if (GreaterThan(fZERO, exponent)) {
124 0 : exponent = fNegate(exponent);
125 0 : bNegated = true;
126 : }
127 :
128 0 : while (GreaterThan(exponent, lower_bound)) {
129 0 : for (i = 0; i < 11; i++) {
130 0 : if (GreaterThan(exponent, GetScaledFraction(k_array[i], 10000))) {
131 0 : exponent = fSubtract(exponent, GetScaledFraction(k_array[i], 10000));
132 0 : solution = fMultiply(solution, GetScaledFraction(expk_array[i], 10000));
133 : }
134 : }
135 : }
136 :
137 : error_term = fAdd(fPositiveOne, exponent);
138 :
139 0 : solution = fMultiply(solution, error_term);
140 :
141 0 : if (bNegated)
142 : solution = fDivide(fPositiveOne, solution);
143 :
144 0 : return solution;
145 : }
146 :
147 0 : static fInt fNaturalLog(fInt value)
148 : {
149 : uint32_t i;
150 0 : fInt upper_bound = Divide(8, 1000);
151 0 : fInt fNegativeOne = ConvertToFraction(-1);
152 : fInt solution = ConvertToFraction(0); /*Starting off with baseline of 0 */
153 : fInt error_term;
154 :
155 : static const uint32_t k_array[10] = {160000, 40000, 20000, 15000, 12500, 11250, 10625, 10313, 10156, 10078};
156 : static const uint32_t logk_array[10] = {27726, 13863, 6931, 4055, 2231, 1178, 606, 308, 155, 78};
157 :
158 0 : while (GreaterThan(fAdd(value, fNegativeOne), upper_bound)) {
159 0 : for (i = 0; i < 10; i++) {
160 0 : if (GreaterThan(value, GetScaledFraction(k_array[i], 10000))) {
161 0 : value = fDivide(value, GetScaledFraction(k_array[i], 10000));
162 0 : solution = fAdd(solution, GetScaledFraction(logk_array[i], 10000));
163 : }
164 : }
165 : }
166 :
167 : error_term = fAdd(fNegativeOne, value);
168 :
169 0 : return (fAdd(solution, error_term));
170 : }
171 :
172 0 : static fInt fDecodeLinearFuse(uint32_t fuse_value, fInt f_min, fInt f_range, uint32_t bitlength)
173 : {
174 0 : fInt f_fuse_value = Convert_ULONG_ToFraction(fuse_value);
175 0 : fInt f_bit_max_value = Convert_ULONG_ToFraction((uPow(2, bitlength)) - 1);
176 :
177 : fInt f_decoded_value;
178 :
179 0 : f_decoded_value = fDivide(f_fuse_value, f_bit_max_value);
180 0 : f_decoded_value = fMultiply(f_decoded_value, f_range);
181 : f_decoded_value = fAdd(f_decoded_value, f_min);
182 :
183 0 : return f_decoded_value;
184 : }
185 :
186 :
187 0 : static fInt fDecodeLogisticFuse(uint32_t fuse_value, fInt f_average, fInt f_range, uint32_t bitlength)
188 : {
189 0 : fInt f_fuse_value = Convert_ULONG_ToFraction(fuse_value);
190 0 : fInt f_bit_max_value = Convert_ULONG_ToFraction((uPow(2, bitlength)) - 1);
191 :
192 0 : fInt f_CONSTANT_NEG13 = ConvertToFraction(-13);
193 0 : fInt f_CONSTANT1 = ConvertToFraction(1);
194 :
195 : fInt f_decoded_value;
196 :
197 0 : f_decoded_value = fSubtract(fDivide(f_bit_max_value, f_fuse_value), f_CONSTANT1);
198 0 : f_decoded_value = fNaturalLog(f_decoded_value);
199 0 : f_decoded_value = fMultiply(f_decoded_value, fDivide(f_range, f_CONSTANT_NEG13));
200 : f_decoded_value = fAdd(f_decoded_value, f_average);
201 :
202 0 : return f_decoded_value;
203 : }
204 :
205 0 : static fInt fDecodeLeakageID (uint32_t leakageID_fuse, fInt ln_max_div_min, fInt f_min, uint32_t bitlength)
206 : {
207 : fInt fLeakage;
208 0 : fInt f_bit_max_value = Convert_ULONG_ToFraction((uPow(2, bitlength)) - 1);
209 :
210 0 : fLeakage = fMultiply(ln_max_div_min, Convert_ULONG_ToFraction(leakageID_fuse));
211 0 : fLeakage = fDivide(fLeakage, f_bit_max_value);
212 0 : fLeakage = fExponential(fLeakage);
213 0 : fLeakage = fMultiply(fLeakage, f_min);
214 :
215 0 : return fLeakage;
216 : }
217 :
218 : static fInt ConvertToFraction(int X) /*Add all range checking here. Is it possible to make fInt a private declaration? */
219 : {
220 : fInt temp;
221 :
222 0 : if (X <= MAX)
223 0 : temp.full = (X << SHIFT_AMOUNT);
224 : else
225 : temp.full = 0;
226 :
227 : return temp;
228 : }
229 :
230 : static fInt fNegate(fInt X)
231 : {
232 0 : fInt CONSTANT_NEGONE = ConvertToFraction(-1);
233 0 : return (fMultiply(X, CONSTANT_NEGONE));
234 : }
235 :
236 : static fInt Convert_ULONG_ToFraction(uint32_t X)
237 : {
238 : fInt temp;
239 :
240 0 : if (X <= MAX)
241 0 : temp.full = (X << SHIFT_AMOUNT);
242 : else
243 : temp.full = 0;
244 :
245 : return temp;
246 : }
247 :
248 0 : static fInt GetScaledFraction(int X, int factor)
249 : {
250 : int times_shifted, factor_shifted;
251 : bool bNEGATED;
252 : fInt fValue;
253 :
254 0 : times_shifted = 0;
255 0 : factor_shifted = 0;
256 0 : bNEGATED = false;
257 :
258 0 : if (X < 0) {
259 0 : X = -1*X;
260 0 : bNEGATED = true;
261 : }
262 :
263 0 : if (factor < 0) {
264 0 : factor = -1*factor;
265 0 : bNEGATED = !bNEGATED; /*If bNEGATED = true due to X < 0, this will cover the case of negative cancelling negative */
266 : }
267 :
268 0 : if ((X > MAX) || factor > MAX) {
269 0 : if ((X/factor) <= MAX) {
270 0 : while (X > MAX) {
271 0 : X = X >> 1;
272 0 : times_shifted++;
273 : }
274 :
275 0 : while (factor > MAX) {
276 0 : factor = factor >> 1;
277 0 : factor_shifted++;
278 : }
279 : } else {
280 0 : fValue.full = 0;
281 0 : return fValue;
282 : }
283 : }
284 :
285 0 : if (factor == 1)
286 : return ConvertToFraction(X);
287 :
288 0 : fValue = fDivide(ConvertToFraction(X * uPow(-1, bNEGATED)), ConvertToFraction(factor));
289 :
290 0 : fValue.full = fValue.full << times_shifted;
291 0 : fValue.full = fValue.full >> factor_shifted;
292 :
293 0 : return fValue;
294 : }
295 :
296 : /* Addition using two fInts */
297 : static fInt fAdd (fInt X, fInt Y)
298 : {
299 : fInt Sum;
300 :
301 0 : Sum.full = X.full + Y.full;
302 :
303 : return Sum;
304 : }
305 :
306 : /* Addition using two fInts */
307 : static fInt fSubtract (fInt X, fInt Y)
308 : {
309 : fInt Difference;
310 :
311 0 : Difference.full = X.full - Y.full;
312 :
313 : return Difference;
314 : }
315 :
316 : static bool Equal(fInt A, fInt B)
317 : {
318 0 : if (A.full == B.full)
319 : return true;
320 : else
321 : return false;
322 : }
323 :
324 : static bool GreaterThan(fInt A, fInt B)
325 : {
326 0 : if (A.full > B.full)
327 : return true;
328 : else
329 : return false;
330 : }
331 :
332 : static fInt fMultiply (fInt X, fInt Y) /* Uses 64-bit integers (int64_t) */
333 : {
334 : fInt Product;
335 : int64_t tempProduct;
336 :
337 : /*The following is for a very specific common case: Non-zero number with ONLY fractional portion*/
338 : /* TEMPORARILY DISABLED - CAN BE USED TO IMPROVE PRECISION
339 : bool X_LessThanOne, Y_LessThanOne;
340 :
341 : X_LessThanOne = (X.partial.real == 0 && X.partial.decimal != 0 && X.full >= 0);
342 : Y_LessThanOne = (Y.partial.real == 0 && Y.partial.decimal != 0 && Y.full >= 0);
343 :
344 : if (X_LessThanOne && Y_LessThanOne) {
345 : Product.full = X.full * Y.full;
346 : return Product
347 : }*/
348 :
349 0 : tempProduct = ((int64_t)X.full) * ((int64_t)Y.full); /*Q(16,16)*Q(16,16) = Q(32, 32) - Might become a negative number! */
350 0 : tempProduct = tempProduct >> 16; /*Remove lagging 16 bits - Will lose some precision from decimal; */
351 0 : Product.full = (int)tempProduct; /*The int64_t will lose the leading 16 bits that were part of the integer portion */
352 :
353 : return Product;
354 : }
355 :
356 : static fInt fDivide (fInt X, fInt Y)
357 : {
358 : fInt fZERO, fQuotient;
359 : int64_t longlongX, longlongY;
360 :
361 0 : fZERO = ConvertToFraction(0);
362 :
363 0 : if (Equal(Y, fZERO))
364 : return fZERO;
365 :
366 0 : longlongX = (int64_t)X.full;
367 0 : longlongY = (int64_t)Y.full;
368 :
369 0 : longlongX = longlongX << 16; /*Q(16,16) -> Q(32,32) */
370 :
371 0 : div64_s64(longlongX, longlongY); /*Q(32,32) divided by Q(16,16) = Q(16,16) Back to original format */
372 :
373 0 : fQuotient.full = (int)longlongX;
374 : return fQuotient;
375 : }
376 :
377 0 : static int ConvertBackToInteger (fInt A) /*THIS is the function that will be used to check with the Golden settings table*/
378 : {
379 : fInt fullNumber, scaledDecimal, scaledReal;
380 :
381 0 : scaledReal.full = GetReal(A) * uPow(10, PRECISION-1); /* DOUBLE CHECK THISSSS!!! */
382 :
383 0 : scaledDecimal.full = uGetScaledDecimal(A);
384 :
385 : fullNumber = fAdd(scaledDecimal,scaledReal);
386 :
387 0 : return fullNumber.full;
388 : }
389 :
390 : static fInt fGetSquare(fInt A)
391 : {
392 0 : return fMultiply(A,A);
393 : }
394 :
395 : /* x_new = x_old - (x_old^2 - C) / (2 * x_old) */
396 0 : static fInt fSqrt(fInt num)
397 : {
398 : fInt F_divide_Fprime, Fprime;
399 : fInt test;
400 : fInt twoShifted;
401 : int seed, counter, error;
402 : fInt x_new, x_old, C, y;
403 :
404 0 : fInt fZERO = ConvertToFraction(0);
405 :
406 : /* (0 > num) is the same as (num < 0), i.e., num is negative */
407 :
408 0 : if (GreaterThan(fZERO, num) || Equal(fZERO, num))
409 0 : return fZERO;
410 :
411 0 : C = num;
412 :
413 0 : if (num.partial.real > 3000)
414 : seed = 60;
415 0 : else if (num.partial.real > 1000)
416 : seed = 30;
417 0 : else if (num.partial.real > 100)
418 : seed = 10;
419 : else
420 0 : seed = 2;
421 :
422 0 : counter = 0;
423 :
424 0 : if (Equal(num, fZERO)) /*Square Root of Zero is zero */
425 0 : return fZERO;
426 :
427 0 : twoShifted = ConvertToFraction(2);
428 : x_new = ConvertToFraction(seed);
429 :
430 : do {
431 0 : counter++;
432 :
433 0 : x_old.full = x_new.full;
434 :
435 0 : test = fGetSquare(x_old); /*1.75*1.75 is reverting back to 1 when shifted down */
436 : y = fSubtract(test, C); /*y = f(x) = x^2 - C; */
437 :
438 0 : Fprime = fMultiply(twoShifted, x_old);
439 0 : F_divide_Fprime = fDivide(y, Fprime);
440 :
441 : x_new = fSubtract(x_old, F_divide_Fprime);
442 :
443 0 : error = ConvertBackToInteger(x_new) - ConvertBackToInteger(x_old);
444 :
445 0 : if (counter > 20) /*20 is already way too many iterations. If we dont have an answer by then, we never will*/
446 0 : return x_new;
447 :
448 0 : } while (uAbs(error) > 0);
449 :
450 0 : return (x_new);
451 : }
452 :
453 0 : static void SolveQuadracticEqn(fInt A, fInt B, fInt C, fInt Roots[])
454 : {
455 0 : fInt *pRoots = &Roots[0];
456 : fInt temp, root_first, root_second;
457 : fInt f_CONSTANT10, f_CONSTANT100;
458 :
459 0 : f_CONSTANT100 = ConvertToFraction(100);
460 : f_CONSTANT10 = ConvertToFraction(10);
461 :
462 0 : while(GreaterThan(A, f_CONSTANT100) || GreaterThan(B, f_CONSTANT100) || GreaterThan(C, f_CONSTANT100)) {
463 0 : A = fDivide(A, f_CONSTANT10);
464 0 : B = fDivide(B, f_CONSTANT10);
465 : C = fDivide(C, f_CONSTANT10);
466 : }
467 :
468 0 : temp = fMultiply(ConvertToFraction(4), A); /* root = 4*A */
469 0 : temp = fMultiply(temp, C); /* root = 4*A*C */
470 0 : temp = fSubtract(fGetSquare(B), temp); /* root = b^2 - 4AC */
471 0 : temp = fSqrt(temp); /*root = Sqrt (b^2 - 4AC); */
472 :
473 0 : root_first = fSubtract(fNegate(B), temp); /* b - Sqrt(b^2 - 4AC) */
474 0 : root_second = fAdd(fNegate(B), temp); /* b + Sqrt(b^2 - 4AC) */
475 :
476 0 : root_first = fDivide(root_first, ConvertToFraction(2)); /* [b +- Sqrt(b^2 - 4AC)]/[2] */
477 0 : root_first = fDivide(root_first, A); /*[b +- Sqrt(b^2 - 4AC)]/[2*A] */
478 :
479 0 : root_second = fDivide(root_second, ConvertToFraction(2)); /* [b +- Sqrt(b^2 - 4AC)]/[2] */
480 0 : root_second = fDivide(root_second, A); /*[b +- Sqrt(b^2 - 4AC)]/[2*A] */
481 :
482 0 : *(pRoots + 0) = root_first;
483 0 : *(pRoots + 1) = root_second;
484 0 : }
485 :
486 : /* -----------------------------------------------------------------------------
487 : * SUPPORT FUNCTIONS
488 : * -----------------------------------------------------------------------------
489 : */
490 :
491 : /* Conversion Functions */
492 : static int GetReal (fInt A)
493 : {
494 0 : return (A.full >> SHIFT_AMOUNT);
495 : }
496 :
497 : static fInt Divide (int X, int Y)
498 : {
499 : fInt A, B, Quotient;
500 :
501 0 : A.full = X << SHIFT_AMOUNT;
502 0 : B.full = Y << SHIFT_AMOUNT;
503 :
504 0 : Quotient = fDivide(A, B);
505 :
506 : return Quotient;
507 : }
508 :
509 0 : static int uGetScaledDecimal (fInt A) /*Converts the fractional portion to whole integers - Costly function */
510 : {
511 : int dec[PRECISION];
512 0 : int i, scaledDecimal = 0, tmp = A.partial.decimal;
513 :
514 0 : for (i = 0; i < PRECISION; i++) {
515 0 : dec[i] = tmp / (1 << SHIFT_AMOUNT);
516 0 : tmp = tmp - ((1 << SHIFT_AMOUNT)*dec[i]);
517 0 : tmp *= 10;
518 0 : scaledDecimal = scaledDecimal + dec[i]*uPow(10, PRECISION - 1 -i);
519 : }
520 :
521 0 : return scaledDecimal;
522 : }
523 :
524 0 : static int uPow(int base, int power)
525 : {
526 0 : if (power == 0)
527 : return 1;
528 : else
529 0 : return (base)*uPow(base, power - 1);
530 : }
531 :
532 : static int uAbs(int X)
533 : {
534 0 : if (X < 0)
535 0 : return (X * -1);
536 : else
537 : return X;
538 : }
539 :
540 : static fInt fRoundUpByStepSize(fInt A, fInt fStepSize, bool error_term)
541 : {
542 : fInt solution;
543 :
544 0 : solution = fDivide(A, fStepSize);
545 0 : solution.partial.decimal = 0; /*All fractional digits changes to 0 */
546 :
547 : if (error_term)
548 : solution.partial.real += 1; /*Error term of 1 added */
549 :
550 0 : solution = fMultiply(solution, fStepSize);
551 : solution = fAdd(solution, fStepSize);
552 :
553 : return solution;
554 : }
555 :
|
