arch/x86/lib/div64.c

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