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 POWERPLAY_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
89 static int uGetScaledDecimal (fInt); /* Internal function */
90 static int GetReal (fInt A); /* Internal function */
91
92 /* -------------------------------------------------------------------------------------
93 * TROUBLESHOOTING INFORMATION
94 * -------------------------------------------------------------------------------------
95 * 1) ConvertToFraction - InputOutOfRangeException: Only accepts numbers smaller than POWERPLAY_MAX (default: 32767)
96 * 2) fAdd - OutputOutOfRangeException: Output bigger than POWERPLAY_MAX (default: 32767)
97 * 3) fMultiply - OutputOutOfRangeException:
98 * 4) fGetSquare - OutputOutOfRangeException:
99 * 5) fDivide - DivideByZeroException
100 * 6) fSqrt - NegativeSquareRootException: Input cannot be a negative number
101 */
102
103 /* -------------------------------------------------------------------------------------
104 * START OF CODE
105 * -------------------------------------------------------------------------------------
106 */
fExponential(fInt exponent)107 static fInt fExponential(fInt exponent) /*Can be used to calculate e^exponent*/
108 {
109 uint32_t i;
110 bool bNegated = false;
111
112 fInt fPositiveOne = ConvertToFraction(1);
113 fInt fZERO = ConvertToFraction(0);
114
115 fInt lower_bound = Divide(78, 10000);
116 fInt solution = fPositiveOne; /*Starting off with baseline of 1 */
117 fInt error_term;
118
119 static const uint32_t k_array[11] = {55452, 27726, 13863, 6931, 4055, 2231, 1178, 606, 308, 155, 78};
120 static const uint32_t expk_array[11] = {2560000, 160000, 40000, 20000, 15000, 12500, 11250, 10625, 10313, 10156, 10078};
121
122 if (GreaterThan(fZERO, exponent)) {
123 exponent = fNegate(exponent);
124 bNegated = true;
125 }
126
127 while (GreaterThan(exponent, lower_bound)) {
128 for (i = 0; i < 11; i++) {
129 if (GreaterThan(exponent, GetScaledFraction(k_array[i], 10000))) {
130 exponent = fSubtract(exponent, GetScaledFraction(k_array[i], 10000));
131 solution = fMultiply(solution, GetScaledFraction(expk_array[i], 10000));
132 }
133 }
134 }
135
136 error_term = fAdd(fPositiveOne, exponent);
137
138 solution = fMultiply(solution, error_term);
139
140 if (bNegated)
141 solution = fDivide(fPositiveOne, solution);
142
143 return solution;
144 }
145
fNaturalLog(fInt value)146 static fInt fNaturalLog(fInt value)
147 {
148 uint32_t i;
149 fInt upper_bound = Divide(8, 1000);
150 fInt fNegativeOne = ConvertToFraction(-1);
151 fInt solution = ConvertToFraction(0); /*Starting off with baseline of 0 */
152 fInt error_term;
153
154 static const uint32_t k_array[10] = {160000, 40000, 20000, 15000, 12500, 11250, 10625, 10313, 10156, 10078};
155 static const uint32_t logk_array[10] = {27726, 13863, 6931, 4055, 2231, 1178, 606, 308, 155, 78};
156
157 while (GreaterThan(fAdd(value, fNegativeOne), upper_bound)) {
158 for (i = 0; i < 10; i++) {
159 if (GreaterThan(value, GetScaledFraction(k_array[i], 10000))) {
160 value = fDivide(value, GetScaledFraction(k_array[i], 10000));
161 solution = fAdd(solution, GetScaledFraction(logk_array[i], 10000));
162 }
163 }
164 }
165
166 error_term = fAdd(fNegativeOne, value);
167
168 return (fAdd(solution, error_term));
169 }
170
fDecodeLinearFuse(uint32_t fuse_value,fInt f_min,fInt f_range,uint32_t bitlength)171 static fInt fDecodeLinearFuse(uint32_t fuse_value, fInt f_min, fInt f_range, uint32_t bitlength)
172 {
173 fInt f_fuse_value = Convert_ULONG_ToFraction(fuse_value);
174 fInt f_bit_max_value = Convert_ULONG_ToFraction((uPow(2, bitlength)) - 1);
175
176 fInt f_decoded_value;
177
178 f_decoded_value = fDivide(f_fuse_value, f_bit_max_value);
179 f_decoded_value = fMultiply(f_decoded_value, f_range);
180 f_decoded_value = fAdd(f_decoded_value, f_min);
181
182 return f_decoded_value;
183 }
184
185
fDecodeLogisticFuse(uint32_t fuse_value,fInt f_average,fInt f_range,uint32_t bitlength)186 static fInt fDecodeLogisticFuse(uint32_t fuse_value, fInt f_average, fInt f_range, uint32_t bitlength)
187 {
188 fInt f_fuse_value = Convert_ULONG_ToFraction(fuse_value);
189 fInt f_bit_max_value = Convert_ULONG_ToFraction((uPow(2, bitlength)) - 1);
190
191 fInt f_CONSTANT_NEG13 = ConvertToFraction(-13);
192 fInt f_CONSTANT1 = ConvertToFraction(1);
193
194 fInt f_decoded_value;
195
196 f_decoded_value = fSubtract(fDivide(f_bit_max_value, f_fuse_value), f_CONSTANT1);
197 f_decoded_value = fNaturalLog(f_decoded_value);
198 f_decoded_value = fMultiply(f_decoded_value, fDivide(f_range, f_CONSTANT_NEG13));
199 f_decoded_value = fAdd(f_decoded_value, f_average);
200
201 return f_decoded_value;
202 }
203
fDecodeLeakageID(uint32_t leakageID_fuse,fInt ln_max_div_min,fInt f_min,uint32_t bitlength)204 static fInt fDecodeLeakageID (uint32_t leakageID_fuse, fInt ln_max_div_min, fInt f_min, uint32_t bitlength)
205 {
206 fInt fLeakage;
207 fInt f_bit_max_value = Convert_ULONG_ToFraction((uPow(2, bitlength)) - 1);
208
209 fLeakage = fMultiply(ln_max_div_min, Convert_ULONG_ToFraction(leakageID_fuse));
210 fLeakage = fDivide(fLeakage, f_bit_max_value);
211 fLeakage = fExponential(fLeakage);
212 fLeakage = fMultiply(fLeakage, f_min);
213
214 return fLeakage;
215 }
216
ConvertToFraction(int X)217 static fInt ConvertToFraction(int X) /*Add all range checking here. Is it possible to make fInt a private declaration? */
218 {
219 fInt temp;
220
221 if (X <= POWERPLAY_MAX)
222 temp.full = (X << SHIFT_AMOUNT);
223 else
224 temp.full = 0;
225
226 return temp;
227 }
228
fNegate(fInt X)229 static fInt fNegate(fInt X)
230 {
231 fInt CONSTANT_NEGONE = ConvertToFraction(-1);
232 return (fMultiply(X, CONSTANT_NEGONE));
233 }
234
Convert_ULONG_ToFraction(uint32_t X)235 static fInt Convert_ULONG_ToFraction(uint32_t X)
236 {
237 fInt temp;
238
239 if (X <= POWERPLAY_MAX)
240 temp.full = (X << SHIFT_AMOUNT);
241 else
242 temp.full = 0;
243
244 return temp;
245 }
246
GetScaledFraction(int X,int factor)247 static fInt GetScaledFraction(int X, int factor)
248 {
249 int times_shifted, factor_shifted;
250 bool bNEGATED;
251 fInt fValue;
252
253 times_shifted = 0;
254 factor_shifted = 0;
255 bNEGATED = false;
256
257 if (X < 0) {
258 X = -1*X;
259 bNEGATED = true;
260 }
261
262 if (factor < 0) {
263 factor = -1*factor;
264 bNEGATED = !bNEGATED; /*If bNEGATED = true due to X < 0, this will cover the case of negative cancelling negative */
265 }
266
267 if ((X > POWERPLAY_MAX) || factor > POWERPLAY_MAX) {
268 if ((X/factor) <= POWERPLAY_MAX) {
269 while (X > POWERPLAY_MAX) {
270 X = X >> 1;
271 times_shifted++;
272 }
273
274 while (factor > POWERPLAY_MAX) {
275 factor = factor >> 1;
276 factor_shifted++;
277 }
278 } else {
279 fValue.full = 0;
280 return fValue;
281 }
282 }
283
284 if (factor == 1)
285 return ConvertToFraction(X);
286
287 fValue = fDivide(ConvertToFraction(X * uPow(-1, bNEGATED)), ConvertToFraction(factor));
288
289 fValue.full = fValue.full << times_shifted;
290 fValue.full = fValue.full >> factor_shifted;
291
292 return fValue;
293 }
294
295 /* Addition using two fInts */
fAdd(fInt X,fInt Y)296 static fInt fAdd (fInt X, fInt Y)
297 {
298 fInt Sum;
299
300 Sum.full = X.full + Y.full;
301
302 return Sum;
303 }
304
305 /* Addition using two fInts */
fSubtract(fInt X,fInt Y)306 static fInt fSubtract (fInt X, fInt Y)
307 {
308 fInt Difference;
309
310 Difference.full = X.full - Y.full;
311
312 return Difference;
313 }
314
Equal(fInt A,fInt B)315 static bool Equal(fInt A, fInt B)
316 {
317 if (A.full == B.full)
318 return true;
319 else
320 return false;
321 }
322
GreaterThan(fInt A,fInt B)323 static bool GreaterThan(fInt A, fInt B)
324 {
325 if (A.full > B.full)
326 return true;
327 else
328 return false;
329 }
330
fMultiply(fInt X,fInt Y)331 static fInt fMultiply (fInt X, fInt Y) /* Uses 64-bit integers (int64_t) */
332 {
333 fInt Product;
334 int64_t tempProduct;
335 bool X_LessThanOne, Y_LessThanOne;
336
337 X_LessThanOne = (X.partial.real == 0 && X.partial.decimal != 0 && X.full >= 0);
338 Y_LessThanOne = (Y.partial.real == 0 && Y.partial.decimal != 0 && Y.full >= 0);
339
340 /*The following is for a very specific common case: Non-zero number with ONLY fractional portion*/
341 /* TEMPORARILY DISABLED - CAN BE USED TO IMPROVE PRECISION
342
343 if (X_LessThanOne && Y_LessThanOne) {
344 Product.full = X.full * Y.full;
345 return Product
346 }*/
347
348 tempProduct = ((int64_t)X.full) * ((int64_t)Y.full); /*Q(16,16)*Q(16,16) = Q(32, 32) - Might become a negative number! */
349 tempProduct = tempProduct >> 16; /*Remove lagging 16 bits - Will lose some precision from decimal; */
350 Product.full = (int)tempProduct; /*The int64_t will lose the leading 16 bits that were part of the integer portion */
351
352 return Product;
353 }
354
fDivide(fInt X,fInt Y)355 static fInt fDivide (fInt X, fInt Y)
356 {
357 fInt fZERO, fQuotient;
358 int64_t longlongX, longlongY;
359
360 fZERO = ConvertToFraction(0);
361
362 if (Equal(Y, fZERO))
363 return fZERO;
364
365 longlongX = (int64_t)X.full;
366 longlongY = (int64_t)Y.full;
367
368 longlongX = longlongX << 16; /*Q(16,16) -> Q(32,32) */
369
370 div64_s64(longlongX, longlongY); /*Q(32,32) divided by Q(16,16) = Q(16,16) Back to original format */
371
372 fQuotient.full = (int)longlongX;
373 return fQuotient;
374 }
375
ConvertBackToInteger(fInt A)376 static int ConvertBackToInteger (fInt A) /*THIS is the function that will be used to check with the Golden settings table*/
377 {
378 fInt fullNumber, scaledDecimal, scaledReal;
379
380 scaledReal.full = GetReal(A) * uPow(10, PRECISION-1); /* DOUBLE CHECK THISSSS!!! */
381
382 scaledDecimal.full = uGetScaledDecimal(A);
383
384 fullNumber = fAdd(scaledDecimal,scaledReal);
385
386 return fullNumber.full;
387 }
388
fGetSquare(fInt A)389 static fInt fGetSquare(fInt A)
390 {
391 return fMultiply(A,A);
392 }
393
394 /* x_new = x_old - (x_old^2 - C) / (2 * x_old) */
fSqrt(fInt num)395 static fInt fSqrt(fInt num)
396 {
397 fInt F_divide_Fprime, Fprime;
398 fInt test;
399 fInt twoShifted;
400 int seed, counter, error;
401 fInt x_new, x_old, C, y;
402
403 fInt fZERO = ConvertToFraction(0);
404
405 /* (0 > num) is the same as (num < 0), i.e., num is negative */
406
407 if (GreaterThan(fZERO, num) || Equal(fZERO, num))
408 return fZERO;
409
410 C = num;
411
412 if (num.partial.real > 3000)
413 seed = 60;
414 else if (num.partial.real > 1000)
415 seed = 30;
416 else if (num.partial.real > 100)
417 seed = 10;
418 else
419 seed = 2;
420
421 counter = 0;
422
423 if (Equal(num, fZERO)) /*Square Root of Zero is zero */
424 return fZERO;
425
426 twoShifted = ConvertToFraction(2);
427 x_new = ConvertToFraction(seed);
428
429 do {
430 counter++;
431
432 x_old.full = x_new.full;
433
434 test = fGetSquare(x_old); /*1.75*1.75 is reverting back to 1 when shifted down */
435 y = fSubtract(test, C); /*y = f(x) = x^2 - C; */
436
437 Fprime = fMultiply(twoShifted, x_old);
438 F_divide_Fprime = fDivide(y, Fprime);
439
440 x_new = fSubtract(x_old, F_divide_Fprime);
441
442 error = ConvertBackToInteger(x_new) - ConvertBackToInteger(x_old);
443
444 if (counter > 20) /*20 is already way too many iterations. If we dont have an answer by then, we never will*/
445 return x_new;
446
447 } while (uAbs(error) > 0);
448
449 return (x_new);
450 }
451
SolveQuadracticEqn(fInt A,fInt B,fInt C,fInt Roots[])452 static void SolveQuadracticEqn(fInt A, fInt B, fInt C, fInt Roots[])
453 {
454 fInt *pRoots = &Roots[0];
455 fInt temp, root_first, root_second;
456 fInt f_CONSTANT10, f_CONSTANT100;
457
458 f_CONSTANT100 = ConvertToFraction(100);
459 f_CONSTANT10 = ConvertToFraction(10);
460
461 while(GreaterThan(A, f_CONSTANT100) || GreaterThan(B, f_CONSTANT100) || GreaterThan(C, f_CONSTANT100)) {
462 A = fDivide(A, f_CONSTANT10);
463 B = fDivide(B, f_CONSTANT10);
464 C = fDivide(C, f_CONSTANT10);
465 }
466
467 temp = fMultiply(ConvertToFraction(4), A); /* root = 4*A */
468 temp = fMultiply(temp, C); /* root = 4*A*C */
469 temp = fSubtract(fGetSquare(B), temp); /* root = b^2 - 4AC */
470 temp = fSqrt(temp); /*root = Sqrt (b^2 - 4AC); */
471
472 root_first = fSubtract(fNegate(B), temp); /* b - Sqrt(b^2 - 4AC) */
473 root_second = fAdd(fNegate(B), temp); /* b + Sqrt(b^2 - 4AC) */
474
475 root_first = fDivide(root_first, ConvertToFraction(2)); /* [b +- Sqrt(b^2 - 4AC)]/[2] */
476 root_first = fDivide(root_first, A); /*[b +- Sqrt(b^2 - 4AC)]/[2*A] */
477
478 root_second = fDivide(root_second, ConvertToFraction(2)); /* [b +- Sqrt(b^2 - 4AC)]/[2] */
479 root_second = fDivide(root_second, A); /*[b +- Sqrt(b^2 - 4AC)]/[2*A] */
480
481 *(pRoots + 0) = root_first;
482 *(pRoots + 1) = root_second;
483 }
484
485 /* -----------------------------------------------------------------------------
486 * SUPPORT FUNCTIONS
487 * -----------------------------------------------------------------------------
488 */
489
490 /* Conversion Functions */
GetReal(fInt A)491 static int GetReal (fInt A)
492 {
493 return (A.full >> SHIFT_AMOUNT);
494 }
495
Divide(int X,int Y)496 static fInt Divide (int X, int Y)
497 {
498 fInt A, B, Quotient;
499
500 A.full = X << SHIFT_AMOUNT;
501 B.full = Y << SHIFT_AMOUNT;
502
503 Quotient = fDivide(A, B);
504
505 return Quotient;
506 }
507
uGetScaledDecimal(fInt A)508 static int uGetScaledDecimal (fInt A) /*Converts the fractional portion to whole integers - Costly function */
509 {
510 int dec[PRECISION];
511 int i, scaledDecimal = 0, tmp = A.partial.decimal;
512
513 for (i = 0; i < PRECISION; i++) {
514 dec[i] = tmp / (1 << SHIFT_AMOUNT);
515 tmp = tmp - ((1 << SHIFT_AMOUNT)*dec[i]);
516 tmp *= 10;
517 scaledDecimal = scaledDecimal + dec[i]*uPow(10, PRECISION - 1 -i);
518 }
519
520 return scaledDecimal;
521 }
522
uPow(int base,int power)523 static int uPow(int base, int power)
524 {
525 if (power == 0)
526 return 1;
527 else
528 return (base)*uPow(base, power - 1);
529 }
530
uAbs(int X)531 static int uAbs(int X)
532 {
533 if (X < 0)
534 return (X * -1);
535 else
536 return X;
537 }
538
fRoundUpByStepSize(fInt A,fInt fStepSize,bool error_term)539 static fInt fRoundUpByStepSize(fInt A, fInt fStepSize, bool error_term)
540 {
541 fInt solution;
542
543 solution = fDivide(A, fStepSize);
544 solution.partial.decimal = 0; /*All fractional digits changes to 0 */
545
546 if (error_term)
547 solution.partial.real += 1; /*Error term of 1 added */
548
549 solution = fMultiply(solution, fStepSize);
550 solution = fAdd(solution, fStepSize);
551
552 return solution;
553 }
554
555