_ Git - BearSSL/blob - src/int/i31_decmod.c

   1 /*
   2  * Copyright (c) 2016 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #include "inner.h"
  26
  27 /* see inner.h */
  28 uint32_t
  29 br_i31_decode_mod(uint32_t *x, const void *src, size_t len, const uint32_t *m)
  30 {
  31         /*
  32          * Two-pass algorithm: in the first pass, we determine whether the
  33          * value fits; in the second pass, we do the actual write.
  34          *
  35          * During the first pass, 'r' contains the comparison result so
  36          * far:
  37          *  0x00000000   value is equal to the modulus
  38          *  0x00000001   value is greater than the modulus
  39          *  0xFFFFFFFF   value is lower than the modulus
  40          *
  41          * Since we iterate starting with the least significant bytes (at
  42          * the end of src[]), each new comparison overrides the previous
  43          * except when the comparison yields 0 (equal).
  44          *
  45          * During the second pass, 'r' is either 0xFFFFFFFF (value fits)
  46          * or 0x00000000 (value does not fit).
  47          *
  48          * We must iterate over all bytes of the source, _and_ possibly
  49          * some extra virtual bytes (with value 0) so as to cover the
  50          * complete modulus as well. We also add 4 such extra bytes beyond
  51          * the modulus length because it then guarantees that no accumulated
  52          * partial word remains to be processed.
  53          */
  54         const unsigned char *buf;
  55         size_t mlen, tlen;
  56         int pass;
  57         uint32_t r;
  58
  59         buf = src;
  60         mlen = (m[0] + 31) >> 5;
  61         tlen = (mlen << 2);
  62         if (tlen < len) {
  63                 tlen = len;
  64         }
  65         tlen += 4;
  66         r = 0;
  67         for (pass = 0; pass < 2; pass ++) {
  68                 size_t u, v;
  69                 uint32_t acc;
  70                 int acc_len;
  71
  72                 v = 1;
  73                 acc = 0;
  74                 acc_len = 0;
  75                 for (u = 0; u < tlen; u ++) {
  76                         uint32_t b;
  77
  78                         if (u < len) {
  79                                 b = buf[len - 1 - u];
  80                         } else {
  81                                 b = 0;
  82                         }
  83                         acc |= (b << acc_len);
  84                         acc_len += 8;
  85                         if (acc_len >= 31) {
  86                                 uint32_t xw;
  87
  88                                 xw = acc & (uint32_t)0x7FFFFFFF;
  89                                 acc_len -= 31;
  90                                 acc = b >> (8 - acc_len);
  91                                 if (v <= mlen) {
  92                                         if (pass) {
  93                                                 x[v] = r & xw;
  94                                         } else {
  95                                                 uint32_t cc;
  96
  97                                                 cc = (uint32_t)CMP(xw, m[v]);
  98                                                 r = MUX(EQ(cc, 0), r, cc);
  99                                         }
 100                                 } else {
 101                                         if (!pass) {
 102                                                 r = MUX(EQ(xw, 0), r, 1);
 103                                         }
 104                                 }
 105                                 v ++;
 106                         }
 107                 }
 108
 109                 /*
 110                  * When we reach this point at the end of the first pass:
 111                  * r is either 0, 1 or -1; we want to set r to 0 if it
 112                  * is equal to 0 or 1, and leave it to -1 otherwise.
 113                  *
 114                  * When we reach this point at the end of the second pass:
 115                  * r is either 0 or -1; we want to leave that value
 116                  * untouched. This is a subcase of the previous.
 117                  */
 118                 r >>= 1;
 119                 r |= (r << 1);
 120         }
 121
 122         x[0] = m[0];
 123         return r & (uint32_t)1;
 124 }