arch/blackfin/lib/udivsi3.S

   1 /*
   2  * Copyright 2004-2009 Analog Devices Inc.
   3  *
   4  * Licensed under the Clear BSD license or the GPL-2 (or later)
   5  */
   6
   7 #include <linux/linkage.h>
   8
   9 #define CARRY AC0
  10
  11 #ifdef CONFIG_ARITHMETIC_OPS_L1
  12 .section .l1.text
  13 #else
  14 .text
  15 #endif
  16
  17
  18 ENTRY(___udivsi3)
  19
  20   CC = R0 < R1 (IU);    /* If X < Y, always return 0 */
  21   IF CC JUMP .Lreturn_ident;
  22
  23   R2 = R1 << 16;
  24   CC = R2 <= R0 (IU);
  25   IF CC JUMP .Lidents;
  26
  27   R2 = R0 >> 31;       /* if X is a 31-bit number */
  28   R3 = R1 >> 15;       /* and Y is a 15-bit number */
  29   R2 = R2 | R3;        /* then it's okay to use the DIVQ builtins (fallthrough to fast)*/
  30   CC = R2;
  31   IF CC JUMP .Ly_16bit;
  32
  33 /* METHOD 1: FAST DIVQ
  34    We know we have a 31-bit dividend, and 15-bit divisor so we can use the
  35    simple divq approach (first setting AQ to 0 - implying unsigned division,
  36    then 16 DIVQ's).
  37 */
  38
  39   AQ = CC;             /* Clear AQ (CC==0) */
  40
  41 /* ISR States: When dividing two integers (32.0/16.0) using divide primitives,
  42    we need to shift the dividend one bit to the left.
  43    We have already checked that we have a 31-bit number so we are safe to do
  44    that.
  45 */
  46   R0 <<= 1;
  47   DIVQ(R0, R1); // 1
  48   DIVQ(R0, R1); // 2
  49   DIVQ(R0, R1); // 3
  50   DIVQ(R0, R1); // 4
  51   DIVQ(R0, R1); // 5
  52   DIVQ(R0, R1); // 6
  53   DIVQ(R0, R1); // 7
  54   DIVQ(R0, R1); // 8
  55   DIVQ(R0, R1); // 9
  56   DIVQ(R0, R1); // 10
  57   DIVQ(R0, R1); // 11
  58   DIVQ(R0, R1); // 12
  59   DIVQ(R0, R1); // 13
  60   DIVQ(R0, R1); // 14
  61   DIVQ(R0, R1); // 15
  62   DIVQ(R0, R1); // 16
  63   R0 = R0.L (Z);
  64   RTS;
  65
  66 .Ly_16bit:
  67   /* We know that the upper 17 bits of Y might have bits set,
  68   ** or that the sign bit of X might have a bit. If Y is a
  69   ** 16-bit number, but not bigger, then we can use the builtins
  70   ** with a post-divide correction.
  71   ** R3 currently holds Y>>15, which means R3's LSB is the
  72   ** bit we're interested in.
  73   */
  74
  75   /* According to the ISR, to use the Divide primitives for
  76   ** unsigned integer divide, the useable range is 31 bits
  77   */
  78   CC = ! BITTST(R0, 31);
  79
  80   /* IF condition is true we can scale our inputs and use the divide primitives,
  81   ** with some post-adjustment
  82   */
  83   R3 += -1;             /* if so, Y is 0x00008nnn */
  84   CC &= AZ;
  85
  86   /* If condition is true we can scale our inputs and use the divide primitives,
  87   ** with some post-adjustment
  88   */
  89   R3 = R1 >> 1;         /* Pre-scaled divisor for primitive case */
  90   R2 = R0 >> 16;
  91
  92   R2 = R3 - R2;         /* shifted divisor < upper 16 bits of dividend */
  93   CC &= CARRY;
  94   IF CC JUMP .Lshift_and_correct;
  95
  96   /* Fall through to the identities */
  97
  98 /* METHOD 2: identities and manual calculation
  99    We are not able to use the divide primites, but may still catch some special
 100    cases.
 101 */
 102 .Lidents:
 103   /* Test for common identities. Value to be returned is placed in R2. */
 104   CC = R0 == 0;        /* 0/Y => 0 */
 105   IF CC JUMP .Lreturn_r0;
 106   CC = R0 == R1;       /* X==Y => 1 */
 107   IF CC JUMP .Lreturn_ident;
 108   CC = R1 == 1;        /* X/1 => X */
 109   IF CC JUMP .Lreturn_ident;
 110
 111   R2.L = ONES R1;
 112   R2 = R2.L (Z);
 113   CC = R2 == 1;
 114   IF CC JUMP .Lpower_of_two;
 115
 116   [--SP] = (R7:5);                /* Push registers R5-R7 */
 117
 118   /* Idents don't match. Go for the full operation. */
 119
 120
 121   R6 = 2;                         /* assume we'll shift two */
 122   R3 = 1;
 123
 124   P2 = R1;
 125                                   /* If either R0 or R1 have sign set, */
 126                                   /* divide them by two, and note it's */
 127                                   /* been done. */
 128   CC = R1 < 0;
 129   R2 = R1 >> 1;
 130   IF CC R1 = R2;                  /* Possibly-shifted R1 */
 131   IF !CC R6 = R3;                 /* R1 doesn't, so at most 1 shifted */
 132
 133   P0 = 0;
 134   R3 = -R1;
 135   [--SP] = R3;
 136   R2 = R0 >> 1;
 137   R2 = R0 >> 1;
 138   CC = R0 < 0;
 139   IF CC P0 = R6;                  /* Number of values divided */
 140   IF !CC R2 = R0;                 /* Shifted R0 */
 141
 142                                   /* P0 is 0, 1 (NR/=2) or 2 (NR/=2, DR/=2) */
 143
 144                                   /* r2 holds Copy dividend  */
 145   R3 = 0;                         /* Clear partial remainder */
 146   R7 = 0;                         /* Initialise quotient bit */
 147
 148   P1 = 32;                        /* Set loop counter */
 149   LSETUP(.Lulst, .Lulend) LC0 = P1; /* Set loop counter */
 150 .Lulst:  R6 = R2 >> 31;             /* R6 = sign bit of R2, for carry */
 151        R2 = R2 << 1;              /* Shift 64 bit dividend up by 1 bit */
 152        R3 = R3 << 1 || R5 = [SP];
 153        R3 = R3 | R6;              /* Include any carry */
 154        CC = R7 < 0;               /* Check quotient(AQ) */
 155                                   /* If AQ==0, we'll sub divisor */
 156        IF CC R5 = R1;             /* and if AQ==1, we'll add it. */
 157        R3 = R3 + R5;              /* Add/sub divsor to partial remainder */
 158        R7 = R3 ^ R1;              /* Generate next quotient bit */
 159
 160        R5 = R7 >> 31;             /* Get AQ */
 161        BITTGL(R5, 0);             /* Invert it, to get what we'll shift */
 162 .Lulend: R2 = R2 + R5;              /* and "shift" it in. */
 163
 164   CC = P0 == 0;                   /* Check how many inputs we shifted */
 165   IF CC JUMP .Lno_mult;            /* if none... */
 166   R6 = R2 << 1;
 167   CC = P0 == 1;
 168   IF CC R2 = R6;                  /* if 1, Q = Q*2 */
 169   IF !CC R1 = P2;                 /* if 2, restore stored divisor */
 170
 171   R3 = R2;                        /* Copy of R2 */
 172   R3 *= R1;                       /* Q * divisor */
 173   R5 = R0 - R3;                   /* Z = (dividend - Q * divisor) */
 174   CC = R1 <= R5 (IU);             /* Check if divisor <= Z? */
 175   R6 = CC;                        /* if yes, R6 = 1 */
 176   R2 = R2 + R6;                   /* if yes, add one to quotient(Q) */
 177 .Lno_mult:
 178   SP += 4;
 179   (R7:5) = [SP++];                /* Pop registers R5-R7 */
 180   R0 = R2;                        /* Store quotient */
 181   RTS;
 182
 183 .Lreturn_ident:
 184   CC = R0 < R1 (IU);    /* If X < Y, always return 0 */
 185   R2 = 0;
 186   IF CC JUMP .Ltrue_return_ident;
 187   R2 = -1 (X);         /* X/0 => 0xFFFFFFFF */
 188   CC = R1 == 0;
 189   IF CC JUMP .Ltrue_return_ident;
 190   R2 = -R2;            /* R2 now 1 */
 191   CC = R0 == R1;       /* X==Y => 1 */
 192   IF CC JUMP .Ltrue_return_ident;
 193   R2 = R0;             /* X/1 => X */
 194   /*FALLTHRU*/
 195
 196 .Ltrue_return_ident:
 197   R0 = R2;
 198 .Lreturn_r0:
 199   RTS;
 200
 201 .Lpower_of_two:
 202   /* Y has a single bit set, which means it's a power of two.
 203   ** That means we can perform the division just by shifting
 204   ** X to the right the appropriate number of bits
 205   */
 206
 207   /* signbits returns the number of sign bits, minus one.
 208   ** 1=>30, 2=>29, ..., 0x40000000=>0. Which means we need
 209   ** to shift right n-signbits spaces. It also means 0x80000000
 210   ** is a special case, because that *also* gives a signbits of 0
 211   */
 212
 213   R2 = R0 >> 31;
 214   CC = R1 < 0;
 215   IF CC JUMP .Ltrue_return_ident;
 216
 217   R1.l = SIGNBITS R1;
 218   R1 = R1.L (Z);
 219   R1 += -30;
 220   R0 = LSHIFT R0 by R1.L;
 221   RTS;
 222
 223 /* METHOD 3: PRESCALE AND USE THE DIVIDE PRIMITIVES WITH SOME POST-CORRECTION
 224   Two scaling operations are required to use the divide primitives with a
 225   divisor > 0x7FFFF.
 226   Firstly (as in method 1) we need to shift the dividend 1 to the left for
 227   integer division.
 228   Secondly we need to shift both the divisor and dividend 1 to the right so
 229   both are in range for the primitives.
 230   The left/right shift of the dividend does nothing so we can skip it.
 231 */
 232 .Lshift_and_correct:
 233   R2 = R0;
 234   // R3 is already R1 >> 1
 235   CC=!CC;
 236   AQ = CC;                        /* Clear AQ, got here with CC = 0 */
 237   DIVQ(R2, R3); // 1
 238   DIVQ(R2, R3); // 2
 239   DIVQ(R2, R3); // 3
 240   DIVQ(R2, R3); // 4
 241   DIVQ(R2, R3); // 5
 242   DIVQ(R2, R3); // 6
 243   DIVQ(R2, R3); // 7
 244   DIVQ(R2, R3); // 8
 245   DIVQ(R2, R3); // 9
 246   DIVQ(R2, R3); // 10
 247   DIVQ(R2, R3); // 11
 248   DIVQ(R2, R3); // 12
 249   DIVQ(R2, R3); // 13
 250   DIVQ(R2, R3); // 14
 251   DIVQ(R2, R3); // 15
 252   DIVQ(R2, R3); // 16
 253
 254   /* According to the Instruction Set Reference:
 255      To divide by a divisor > 0x7FFF,
 256      1. prescale and perform divide to obtain quotient (Q) (done above),
 257      2. multiply quotient by unscaled divisor (result M)
 258      3. subtract the product from the divident to get an error (E = X - M)
 259      4. if E < divisor (Y) subtract 1, if E > divisor (Y) add 1, else return quotient (Q)
 260    */
 261   R3 = R2.L (Z);                /* Q = X' / Y' */
 262   R2 = R3;              /* Preserve Q */
 263   R2 *= R1;             /* M = Q * Y */
 264   R2 = R0 - R2;         /* E = X - M */
 265   R0 = R3;              /* Copy Q into result reg */
 266
 267 /* Correction: If result of the multiply is negative, we overflowed
 268    and need to correct the result by subtracting 1 from the result.*/
 269   R3 = 0xFFFF (Z);
 270   R2 = R2 >> 16;                /* E >> 16 */
 271   CC = R2 == R3;
 272   R3 = 1 ;
 273   R1 = R0 - R3;
 274   IF CC R0 = R1;
 275   RTS;
 276
 277 ENDPROC(___udivsi3)