ArmPkg/Library/CompilerIntrinsicsLib/Arm/udivmoddi4.c

   1 /** @file
   2   Compiler intrinsic for 64-bit compare, ported from LLVM code.
   3
   4   Copyright (c) 2008-2009, Apple Inc. All rights reserved.<BR>
   5
   6   SPDX-License-Identifier: BSD-2-Clause-Patent
   7
   8 **/
   9 /**
  10   University of Illinois/NCSA
  11   Open Source License
  12
  13   Copyright (c) 2003-2008 University of Illinois at Urbana-Champaign.
  14   All rights reserved.
  15
  16   Developed by:
  17
  18       LLVM Team
  19
  20       University of Illinois at Urbana-Champaign
  21
  22       http://llvm.org
  23
  24   Permission is hereby granted, free of charge, to any person obtaining a copy of
  25   this software and associated documentation files (the "Software"), to deal with
  26   the Software without restriction, including without limitation the rights to
  27   use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
  28   of the Software, and to permit persons to whom the Software is furnished to do
  29   so, subject to the following conditions:
  30
  31       * Redistributions of source code must retain the above copyright notice,
  32         this list of conditions and the following disclaimers.
  33
  34       * Redistributions in binary form must reproduce the above copyright notice,
  35         this list of conditions and the following disclaimers in the
  36         documentation and/or other materials provided with the distribution.
  37
  38       * Neither the names of the LLVM Team, University of Illinois at
  39         Urbana-Champaign, nor the names of its contributors may be used to
  40         endorse or promote products derived from this Software without specific
  41         prior written permission.
  42
  43   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  44   IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
  45   FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  46   CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  47   LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  48   OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE
  49   SOFTWARE.
  50 **/
  51
  52
  53 #include "Llvm_int_lib.h"
  54
  55 // Effects: if rem != 0, *rem = a % b
  56 // Returns: a / b
  57
  58 // Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide
  59
  60 UINT64
  61 __udivmoddi4 (UINT64 a, UINT64 b, UINT64* rem)
  62 {
  63     const unsigned n_uword_bits = sizeof(UINT32) * CHAR_BIT;
  64     const unsigned n_udword_bits = sizeof(UINT64) * CHAR_BIT;
  65     udwords n;
  66     n.all = a;
  67     udwords d;
  68     d.all = b;
  69     udwords q;
  70     udwords r;
  71     unsigned sr;
  72
  73     if (b == 0) {
  74 //      ASSERT (FALSE);
  75       return 0;
  76     }
  77
  78     // special cases, X is unknown, K != 0
  79     if (n.high == 0)
  80     {
  81         if (d.high == 0)
  82         {
  83             // 0 X
  84             // ---
  85             // 0 X
  86             if (rem)
  87                 *rem = n.low % d.low;
  88             return n.low / d.low;
  89         }
  90         // 0 X
  91         // ---
  92         // K X
  93         if (rem)
  94             *rem = n.low;
  95         return 0;
  96     }
  97     // n.high != 0
  98     if (d.low == 0)
  99     {
 100         if (d.high == 0)
 101         {
 102             // K X
 103             // ---
 104             // 0 0
 105             if (rem)
 106                 *rem = n.high % d.low;
 107             return n.high / d.low;
 108         }
 109         // d.high != 0
 110         if (n.low == 0)
 111         {
 112             // K 0
 113             // ---
 114             // K 0
 115             if (rem)
 116             {
 117                 r.high = n.high % d.high;
 118                 r.low = 0;
 119                 *rem = r.all;
 120             }
 121             return n.high / d.high;
 122         }
 123         // K K
 124         // ---
 125         // K 0
 126         if ((d.high & (d.high - 1)) == 0)     // if d is a power of 2
 127         {
 128             if (rem)
 129             {
 130                 r.low = n.low;
 131                 r.high = n.high & (d.high - 1);
 132                 *rem = r.all;
 133             }
 134             return n.high >> COUNT_TRAILING_ZEROS(d.high);
 135         }
 136         // K K
 137         // ---
 138         // K 0
 139         sr = COUNT_LEADING_ZEROS(d.high) - COUNT_LEADING_ZEROS(n.high);
 140         // 0 <= sr <= n_uword_bits - 2 or sr large
 141         if (sr > n_uword_bits - 2)
 142         {
 143            if (rem)
 144                 *rem = n.all;
 145             return 0;
 146         }
 147         ++sr;
 148         // 1 <= sr <= n_uword_bits - 1
 149         // q.all = n.all << (n_udword_bits - sr);
 150         q.low = 0;
 151         q.high = n.low << (n_uword_bits - sr);
 152         // r.all = n.all >> sr;
 153         r.high = n.high >> sr;
 154         r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr);
 155     }
 156     else  // d.low != 0
 157     {
 158         if (d.high == 0)
 159         {
 160             // K X
 161             // ---
 162             // 0 K
 163             if ((d.low & (d.low - 1)) == 0)     // if d is a power of 2
 164             {
 165                 if (rem)
 166                     *rem = n.low & (d.low - 1);
 167                 if (d.low == 1)
 168                     return n.all;
 169                 unsigned sr = COUNT_TRAILING_ZEROS(d.low);
 170                 q.high = n.high >> sr;
 171                 q.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr);
 172                 return q.all;
 173             }
 174             // K X
 175             // ---
 176             // 0 K
 177             sr = 1 + n_uword_bits + COUNT_LEADING_ZEROS(d.low) - COUNT_LEADING_ZEROS(n.high);
 178             // 2 <= sr <= n_udword_bits - 1
 179             // q.all = n.all << (n_udword_bits - sr);
 180             // r.all = n.all >> sr;
 181             // if (sr == n_uword_bits)
 182             // {
 183             //     q.low = 0;
 184             //     q.high = n.low;
 185             //     r.high = 0;
 186             //     r.low = n.high;
 187             // }
 188             // else if (sr < n_uword_bits)  // 2 <= sr <= n_uword_bits - 1
 189             // {
 190             //     q.low = 0;
 191             //     q.high = n.low << (n_uword_bits - sr);
 192             //     r.high = n.high >> sr;
 193             //     r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr);
 194             // }
 195             // else              // n_uword_bits + 1 <= sr <= n_udword_bits - 1
 196             // {
 197             //     q.low = n.low << (n_udword_bits - sr);
 198             //     q.high = (n.high << (n_udword_bits - sr)) |
 199             //              (n.low >> (sr - n_uword_bits));
 200             //     r.high = 0;
 201             //     r.low = n.high >> (sr - n_uword_bits);
 202             // }
 203             q.low =  (n.low << (n_udword_bits - sr)) &
 204                      ((INT32)(n_uword_bits - sr) >> (n_uword_bits-1));
 205             q.high = ((n.low << ( n_uword_bits - sr))                       &
 206                      ((INT32)(sr - n_uword_bits - 1) >> (n_uword_bits-1))) |
 207                      (((n.high << (n_udword_bits - sr))                     |
 208                      (n.low >> (sr - n_uword_bits)))                        &
 209                      ((INT32)(n_uword_bits - sr) >> (n_uword_bits-1)));
 210             r.high = (n.high >> sr) &
 211                      ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1));
 212             r.low =  ((n.high >> (sr - n_uword_bits))                       &
 213                      ((INT32)(n_uword_bits - sr - 1) >> (n_uword_bits-1))) |
 214                      (((n.high << (n_uword_bits - sr))                      |
 215                      (n.low >> sr))                                         &
 216                      ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1)));
 217         }
 218         else
 219         {
 220             // K X
 221             // ---
 222             // K K
 223             sr = COUNT_LEADING_ZEROS(d.high) - COUNT_LEADING_ZEROS(n.high);
 224             // 0 <= sr <= n_uword_bits - 1 or sr large
 225             if (sr > n_uword_bits - 1)
 226             {
 227                if (rem)
 228                     *rem = n.all;
 229                 return 0;
 230             }
 231             ++sr;
 232             // 1 <= sr <= n_uword_bits
 233             // q.all = n.all << (n_udword_bits - sr);
 234             q.low = 0;
 235             q.high = n.low << (n_uword_bits - sr);
 236             // r.all = n.all >> sr;
 237             // if (sr < n_uword_bits)
 238             // {
 239             //     r.high = n.high >> sr;
 240             //     r.low = (n.high << (n_uword_bits - sr)) | (n.low >> sr);
 241             // }
 242             // else
 243             // {
 244             //     r.high = 0;
 245             //     r.low = n.high;
 246             // }
 247             r.high = (n.high >> sr) &
 248                      ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1));
 249             r.low = (n.high << (n_uword_bits - sr)) |
 250                     ((n.low >> sr)                  &
 251                     ((INT32)(sr - n_uword_bits) >> (n_uword_bits-1)));
 252         }
 253     }
 254     // Not a special case
 255     // q and r are initialized with:
 256     // q.all = n.all << (n_udword_bits - sr);
 257     // r.all = n.all >> sr;
 258     // 1 <= sr <= n_udword_bits - 1
 259     UINT32 carry = 0;
 260     for (; sr > 0; --sr)
 261     {
 262         // r:q = ((r:q)  << 1) | carry
 263         r.high = (r.high << 1) | (r.low  >> (n_uword_bits - 1));
 264         r.low  = (r.low  << 1) | (q.high >> (n_uword_bits - 1));
 265         q.high = (q.high << 1) | (q.low  >> (n_uword_bits - 1));
 266         q.low  = (q.low  << 1) | carry;
 267         // carry = 0;
 268         // if (r.all >= d.all)
 269         // {
 270         //      r.all -= d.all;
 271         //      carry = 1;
 272         // }
 273         const INT64 s = (INT64)(d.all - r.all - 1) >> (n_udword_bits - 1);
 274         carry = s & 1;
 275         r.all -= d.all & s;
 276     }
 277     q.all = (q.all << 1) | carry;
 278     if (rem)
 279         *rem = r.all;
 280     return q.all;
 281 }