text: /*
   * Encoding/decoding of keys and signatures.
   *
   * ==========================(LICENSE BEGIN)============================
   *
   * Copyright (c) 2017-2019  Falcon Project
   *
   * Permission is hereby granted, free of charge, to any person obtaining
   * a copy of this software and associated documentation files (the
   * "Software"), to deal in the Software without restriction, including
   * without limitation the rights to use, copy, modify, merge, publish,
   * distribute, sublicense, and/or sell copies of the Software, and to
   * permit persons to whom the Software is furnished to do so, subject to
   * the following conditions:
   *
   * The above copyright notice and this permission notice shall be
   * included in all copies or substantial portions of the Software.
   *
   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
   * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
   * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
   * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
   * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
   * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
   * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
   *
   * ===========================(LICENSE END)=============================
   *
   * @author   Thomas Pornin <thomas.pornin@nccgroup.com>
   */
  
  #include "inner.h"
  
  /* see inner.h */
  size_t
  modq_encode(
      void *out, size_t max_out_len,
      const uint16_t *x, unsigned logn) {
      size_t n, out_len, u;
      uint8_t *buf;
      uint32_t acc;
      int acc_len;
  
      n = (size_t)1 << logn;
      for (u = 0; u < n; u ++) {
          if (x[u] >= 12289) {
              return 0;
          }
      }
      out_len = ((n * 14) + 7) >> 3;
      if (out == NULL) {
          return out_len;
      }
      if (out_len > max_out_len) {
          return 0;
      }
      buf = out;
      acc = 0;
      acc_len = 0;
      for (u = 0; u < n; u ++) {
          acc = (acc << 14) | x[u];
          acc_len += 14;
          while (acc_len >= 8) {
              acc_len -= 8;
              *buf ++ = (uint8_t)(acc >> acc_len);
          }
      }
      if (acc_len > 0) {
          *buf = (uint8_t)(acc << (8 - acc_len));
      }
      return out_len;
  }
  
  /* see inner.h */
  size_t
  modq_decode(
      uint16_t *x, unsigned logn,
      const void *in, size_t max_in_len) {
      size_t n, in_len, u;
      const uint8_t *buf;
      uint32_t acc;
      int acc_len;
  
      n = (size_t)1 << logn;
      in_len = ((n * 14) + 7) >> 3;
      if (in_len > max_in_len) {
          return 0;
      }
      buf = in;
      acc = 0;
      acc_len = 0;
      u = 0;
      while (u < n) {
          acc = (acc << 8) | (*buf ++);
          acc_len += 8;
          if (acc_len >= 14) {
              unsigned w;
  
              acc_len -= 14;
              w = (acc >> acc_len) & 0x3FFF;
              if (w >= 12289) {
                  return 0;
              }
              x[u ++] = (uint16_t)w;
          }
      }
      if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
          return 0;
      }
      return in_len;
  }
  
  /* see inner.h */
  size_t
  trim_i16_encode(
      void *out, size_t max_out_len,
      const int16_t *x, unsigned logn, unsigned bits) {
      size_t n, u, out_len;
      int minv, maxv;
      uint8_t *buf;
      uint32_t acc, mask;
      unsigned acc_len;
  
      n = (size_t)1 << logn;
      maxv = (1 << (bits - 1)) - 1;
      minv = -maxv;
      for (u = 0; u < n; u ++) {
          if (x[u] < minv || x[u] > maxv) {
              return 0;
          }
      }
      out_len = ((n * bits) + 7) >> 3;
      if (out == NULL) {
          return out_len;
      }
      if (out_len > max_out_len) {
          return 0;
      }
      buf = out;
      acc = 0;
      acc_len = 0;
      mask = ((uint32_t)1 << bits) - 1;
      for (u = 0; u < n; u ++) {
          acc = (acc << bits) | ((uint16_t)x[u] & mask);
          acc_len += bits;
          while (acc_len >= 8) {
              acc_len -= 8;
              *buf ++ = (uint8_t)(acc >> acc_len);
          }
      }
      if (acc_len > 0) {
          *buf ++ = (uint8_t)(acc << (8 - acc_len));
      }
      return out_len;
  }
  
  /* see inner.h */
  size_t
  trim_i16_decode(
      int16_t *x, unsigned logn, unsigned bits,
      const void *in, size_t max_in_len) {
      size_t n, in_len;
      const uint8_t *buf;
      size_t u;
      uint32_t acc, mask1, mask2;
      unsigned acc_len;
  
      n = (size_t)1 << logn;
      in_len = ((n * bits) + 7) >> 3;
      if (in_len > max_in_len) {
          return 0;
      }
      buf = in;
      u = 0;
      acc = 0;
      acc_len = 0;
      mask1 = ((uint32_t)1 << bits) - 1;
      mask2 = (uint32_t)1 << (bits - 1);
      while (u < n) {
          acc = (acc << 8) | *buf ++;
          acc_len += 8;
          while (acc_len >= bits && u < n) {
              uint32_t w;
  
              acc_len -= bits;
              w = (acc >> acc_len) & mask1;
              w |= -(w & mask2);
              if (w == -mask2) {
                  /*
                   * The -2^(bits-1) value is forbidden.
                   */
                  return 0;
              }
              w |= -(w & mask2);
              x[u ++] = (int16_t) * (int32_t *)&w;
          }
      }
      if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
          /*
           * Extra bits in the last byte must be zero.
           */
          return 0;
      }
      return in_len;
  }
  
  /* see inner.h */
  size_t
  trim_i8_encode(
      void *out, size_t max_out_len,
      const int8_t *x, unsigned logn, unsigned bits) {
      size_t n, u, out_len;
      int minv, maxv;
      uint8_t *buf;
      uint32_t acc, mask;
      unsigned acc_len;
  
      n = (size_t)1 << logn;
      maxv = (1 << (bits - 1)) - 1;
      minv = -maxv;
      for (u = 0; u < n; u ++) {
          if (x[u] < minv || x[u] > maxv) {
              return 0;
          }
      }
      out_len = ((n * bits) + 7) >> 3;
      if (out == NULL) {
          return out_len;
      }
      if (out_len > max_out_len) {
          return 0;
      }
      buf = out;
      acc = 0;
      acc_len = 0;
      mask = ((uint32_t)1 << bits) - 1;
      for (u = 0; u < n; u ++) {
          acc = (acc << bits) | ((uint8_t)x[u] & mask);
          acc_len += bits;
          while (acc_len >= 8) {
              acc_len -= 8;
              *buf ++ = (uint8_t)(acc >> acc_len);
          }
      }
      if (acc_len > 0) {
          *buf ++ = (uint8_t)(acc << (8 - acc_len));
      }
      return out_len;
  }
  
  /* see inner.h */
  size_t
  trim_i8_decode(
      int8_t *x, unsigned logn, unsigned bits,
      const void *in, size_t max_in_len) {
      size_t n, in_len;
      const uint8_t *buf;
      size_t u;
      uint32_t acc, mask1, mask2;
      unsigned acc_len;
  
      n = (size_t)1 << logn;
      in_len = ((n * bits) + 7) >> 3;
      if (in_len > max_in_len) {
          return 0;
      }
      buf = in;
      u = 0;
      acc = 0;
      acc_len = 0;
      mask1 = ((uint32_t)1 << bits) - 1;
      mask2 = (uint32_t)1 << (bits - 1);
      while (u < n) {
          acc = (acc << 8) | *buf ++;
          acc_len += 8;
          while (acc_len >= bits && u < n) {
              uint32_t w;
  
              acc_len -= bits;
              w = (acc >> acc_len) & mask1;
              w |= -(w & mask2);
              if (w == -mask2) {
                  /*
                   * The -2^(bits-1) value is forbidden.
                   */
                  return 0;
              }
              x[u ++] = (int8_t) * (int32_t *)&w;
          }
      }
      if ((acc & (((uint32_t)1 << acc_len) - 1)) != 0) {
          /*
           * Extra bits in the last byte must be zero.
           */
          return 0;
      }
      return in_len;
  }
  
  /* see inner.h */
  size_t
  comp_encode(
      void *out, size_t max_out_len,
      const int16_t *x, unsigned logn) {
      uint8_t *buf;
      size_t n, u, v;
      uint32_t acc;
      unsigned acc_len;
  
      n = (size_t)1 << logn;
      buf = out;
  
      /*
       * Make sure that all values are within the -2047..+2047 range.
       */
      for (u = 0; u < n; u ++) {
          if (x[u] < -2047 || x[u] > +2047) {
              return 0;
          }
      }
  
      acc = 0;
      acc_len = 0;
      v = 0;
      for (u = 0; u < n; u ++) {
          int t;
          unsigned w;
  
          /*
           * Get sign and absolute value of next integer; push the
           * sign bit.
           */
          acc <<= 1;
          t = x[u];
          if (t < 0) {
              t = -t;
              acc |= 1;
          }
          w = (unsigned)t;
  
          /*
           * Push the low 7 bits of the absolute value.
           */
          acc <<= 7;
          acc |= w & 127u;
          w >>= 7;
  
          /*
           * We pushed exactly 8 bits.
           */
          acc_len += 8;
  
          /*
           * Push as many zeros as necessary, then a one. Since the
           * absolute value is at most 2047, w can only range up to
           * 15 at this point, thus we will add at most 16 bits
           * here. With the 8 bits above and possibly up to 7 bits
           * from previous iterations, we may go up to 31 bits, which
           * will fit in the accumulator, which is an uint32_t.
           */
          acc <<= (w + 1);
          acc |= 1;
          acc_len += w + 1;
  
          /*
           * Produce all full bytes.
           */
          while (acc_len >= 8) {
              acc_len -= 8;
              if (buf != NULL) {
                  if (v >= max_out_len) {
                      return 0;
                  }
                  buf[v] = (uint8_t)(acc >> acc_len);
              }
              v ++;
          }
      }
  
      /*
       * Flush remaining bits (if any).
       */
      if (acc_len > 0) {
          if (buf != NULL) {
              if (v >= max_out_len) {
                  return 0;
              }
              buf[v] = (uint8_t)(acc << (8 - acc_len));
          }
          v ++;
      }
  
      return v;
  }
  
  /* see inner.h */
  size_t
  comp_decode(
      int16_t *x, unsigned logn,
      const void *in, size_t max_in_len) {
      const uint8_t *buf;
      size_t n, u, v;
      uint32_t acc;
      unsigned acc_len;
  
      n = (size_t)1 << logn;
      buf = in;
      acc = 0;
      acc_len = 0;
      v = 0;
      for (u = 0; u < n; u ++) {
          unsigned b, s, m;
  
          /*
           * Get next eight bits: sign and low seven bits of the
           * absolute value.
           */
          if (v >= max_in_len) {
              return 0;
          }
          acc = (acc << 8) | (uint32_t)buf[v ++];
          b = acc >> acc_len;
          s = b & 128;
          m = b & 127;
  
          /*
           * Get next bits until a 1 is reached.
           */
          for (;;) {
              if (acc_len == 0) {
                  if (v >= max_in_len) {
                      return 0;
                  }
                  acc = (acc << 8) | (uint32_t)buf[v ++];
                  acc_len = 8;
              }
              acc_len --;
              if (((acc >> acc_len) & 1) != 0) {
                  break;
              }
              m += 128;
              if (m > 2047) {
                  return 0;
              }
          }
          x[u] = (int16_t)(s ? -(int)m : (int)m);
      }
      return v;
  }
  
  /*
   * Key elements and signatures are polynomials with small integer
   * coefficients. Here are some statistics gathered over many
   * generated key pairs (10000 or more for each degree):
   *
   *   log(n)     n   max(f,g)   std(f,g)   max(F,G)   std(F,G)
   *      1       2     129       56.31       143       60.02
   *      2       4     123       40.93       160       46.52
   *      3       8      97       28.97       159       38.01
   *      4      16     100       21.48       154       32.50
   *      5      32      71       15.41       151       29.36
   *      6      64      59       11.07       138       27.77
   *      7     128      39        7.91       144       27.00
   *      8     256      32        5.63       148       26.61
   *      9     512      22        4.00       137       26.46
   *     10    1024      15        2.84       146       26.41
   *
   * We want a compact storage format for private key, and, as part of
   * key generation, we are allowed to reject some keys which would
   * otherwise be fine (this does not induce any noticeable vulnerability
   * as long as we reject only a small proportion of possible keys).
   * Hence, we enforce at key generation time maximum values for the
   * elements of f, g, F and G, so that their encoding can be expressed
   * in fixed-width values. Limits have been chosen so that generated
   * keys are almost always within bounds, thus not impacting neither
   * security or performance.
   *
   * IMPORTANT: the code assumes that all coefficients of f, g, F and G
   * ultimately fit in the -127..+127 range. Thus, none of the elements
   * of max_fg_bits[] and max_FG_bits[] shall be greater than 8.
   */
  
  const uint8_t max_fg_bits[] = {
      0, /* unused */
      8,
      8,
      8,
      8,
      8,
      7,
      7,
      6,
      6,
      5
  };
  
  const uint8_t max_FG_bits[] = {
      0, /* unused */
      8,
      8,
      8,
      8,
      8,
      8,
      8,
      8,
      8,
      8
  };
  
  /*
   * When generating a new key pair, we can always reject keys which
   * feature an abnormally large coefficient. This can also be done for
   * signatures, albeit with some care: in case the signature process is
   * used in a derandomized setup (explicitly seeded with the message and
   * private key), we have to follow the specification faithfully, and the
   * specification only enforces a limit on the L2 norm of the signature
   * vector. The limit on the L2 norm implies that the absolute value of
   * a coefficient of the signature cannot be more than the following:
   *
   *   log(n)     n   max sig coeff (theoretical)
   *      1       2       412
   *      2       4       583
   *      3       8       824
   *      4      16      1166
   *      5      32      1649
   *      6      64      2332
   *      7     128      3299
   *      8     256      4665
   *      9     512      6598
   *     10    1024      9331
   *
   * However, the largest observed signature coefficients during our
   * experiments was 1077 (in absolute value), hence we can assume that,
   * with overwhelming probability, signature coefficients will fit
   * in -2047..2047, i.e. 12 bits.
   */
  
  const uint8_t max_sig_bits[] = {
      0, /* unused */
      10,
      11,
      11,
      12,
      12,
      12,
      12,
      12,
      12,
      12
  };
  