arch/x86/lib/div64.c

   1 // SPDX-License-Identifier: BSD-3-Clause
   2 /*
   3  * This file is copied from the coreboot repository as part of
   4  * the libpayload project:
   5  *
   6  * Copyright 2014 Google Inc.
   7  */
   8
   9 #include <common.h>
  10
  11 union overlay64 {
  12         u64 longw;
  13         struct {
  14                 u32 lower;
  15                 u32 higher;
  16         } words;
  17 };
  18
  19 u64 __ashldi3(u64 num, unsigned int shift)
  20 {
  21         union overlay64 output;
  22
  23         output.longw = num;
  24         if (shift >= 32) {
  25                 output.words.higher = output.words.lower << (shift - 32);
  26                 output.words.lower = 0;
  27         } else {
  28                 if (!shift)
  29                         return num;
  30                 output.words.higher = (output.words.higher << shift) |
  31                         (output.words.lower >> (32 - shift));
  32                 output.words.lower = output.words.lower << shift;
  33         }
  34         return output.longw;
  35 }
  36
  37 u64 __lshrdi3(u64 num, unsigned int shift)
  38 {
  39         union overlay64 output;
  40
  41         output.longw = num;
  42         if (shift >= 32) {
  43                 output.words.lower = output.words.higher >> (shift - 32);
  44                 output.words.higher = 0;
  45         } else {
  46                 if (!shift)
  47                         return num;
  48                 output.words.lower = output.words.lower >> shift |
  49                         (output.words.higher << (32 - shift));
  50                 output.words.higher = output.words.higher >> shift;
  51         }
  52         return output.longw;
  53 }
  54
  55 #define MAX_32BIT_UINT ((((u64)1) << 32) - 1)
  56
  57 static u64 _64bit_divide(u64 dividend, u64 divider, u64 *rem_p)
  58 {
  59         u64 result = 0;
  60
  61         /*
  62          * If divider is zero - let the rest of the system care about the
  63          * exception.
  64          */
  65         if (!divider)
  66                 return 1 / (u32)divider;
  67
  68         /* As an optimization, let's not use 64 bit division unless we must. */
  69         if (dividend <= MAX_32BIT_UINT) {
  70                 if (divider > MAX_32BIT_UINT) {
  71                         result = 0;
  72                         if (rem_p)
  73                                 *rem_p = divider;
  74                 } else {
  75                         result = (u32)dividend / (u32)divider;
  76                         if (rem_p)
  77                                 *rem_p = (u32)dividend % (u32)divider;
  78                 }
  79                 return result;
  80         }
  81
  82         while (divider <= dividend) {
  83                 u64 locald = divider;
  84                 u64 limit = __lshrdi3(dividend, 1);
  85                 int shifts = 0;
  86
  87                 while (locald <= limit) {
  88                         shifts++;
  89                         locald = locald + locald;
  90                 }
  91                 result |= __ashldi3(1, shifts);
  92                 dividend -= locald;
  93         }
  94
  95         if (rem_p)
  96                 *rem_p = dividend;
  97
  98         return result;
  99 }
 100
 101 u64 __udivdi3(u64 num, u64 den)
 102 {
 103         return _64bit_divide(num, den, NULL);
 104 }
 105
 106 u64 __umoddi3(u64 num, u64 den)
 107 {
 108         u64 v = 0;
 109
 110         _64bit_divide(num, den, &v);
 111         return v;
 112 }