sdcc/support/regression/tests/bug-3296.c

   1 /*
   2    bug-3229.c
   3    A crash in code generation for stm8 in the modular inversion of the NTRU reference implementation.
   4  */
   5
   6 #include <testfwk.h>
   7
   8 #include <stdint.h>
   9 #include <stddef.h>
  10
  11 #define NTRU_N 67 // Smallest prime for which the bug could be reproduced.
  12
  13 typedef struct{
  14   uint16_t coeffs[NTRU_N];
  15 } poly;
  16
  17 static inline uint8_t mod3(uint8_t a) /* a between 0 and 9 */
  18 {
  19   int16_t t, c;
  20   a = (a >> 2) + (a & 3); /* between 0 and 4 */
  21   t = a - 3;
  22   c = t >> 5;
  23   return (uint8_t) (t^(c&(a^t)));
  24 }
  25
  26 /* return -1 if x<0 and y<0; otherwise return 0 */
  27 static inline int16_t both_negative_mask(int16_t x,int16_t y)
  28 {
  29   return (x & y) >> 15;
  30 }
  31
  32 #if !defined(__SDCC_mcs51) && !defined(__SDCC_sm83) && !defined(__SDCC_pdk13) && !defined(__SDCC_pdk14) && !defined(__SDCC_pdk15) && !defined(__SDCC_pdk16) // Lack of memory
  33 void poly_S3_inv(poly *r, const poly *a)
  34 {
  35   poly f, g, v, w;
  36   size_t i,loop;
  37   int16_t delta,sign,swap,t;
  38
  39   for (i = 0;i < NTRU_N;++i) v.coeffs[i] = 0;
  40   for (i = 0;i < NTRU_N;++i) w.coeffs[i] = 0;
  41   w.coeffs[0] = 1;
  42
  43   for (i = 0;i < NTRU_N;++i) f.coeffs[i] = 1;
  44   for (i = 0;i < NTRU_N-1;++i) g.coeffs[NTRU_N-2-i] = mod3((a->coeffs[i] & 3) + 2*(a->coeffs[NTRU_N-1] & 3));
  45   g.coeffs[NTRU_N-1] = 0;
  46
  47   delta = 1;
  48
  49   for (loop = 0;loop < 2*(NTRU_N-1)-1;++loop) {
  50     for (i = NTRU_N-1;i > 0;--i) v.coeffs[i] = v.coeffs[i-1];
  51     v.coeffs[0] = 0;
  52
  53     sign = mod3((uint8_t) (2 * g.coeffs[0] * f.coeffs[0]));
  54     swap = both_negative_mask(-delta,-(int16_t) g.coeffs[0]);
  55     delta ^= swap & (delta ^ -delta);
  56     delta += 1;
  57
  58     for (i = 0;i < NTRU_N;++i) {
  59       t = swap&(f.coeffs[i]^g.coeffs[i]); f.coeffs[i] ^= t; g.coeffs[i] ^= t;
  60       t = swap&(v.coeffs[i]^w.coeffs[i]); v.coeffs[i] ^= t; w.coeffs[i] ^= t;
  61     }
  62
  63     for (i = 0;i < NTRU_N;++i) g.coeffs[i] = mod3((uint8_t) (g.coeffs[i]+sign*f.coeffs[i]));
  64     for (i = 0;i < NTRU_N;++i) w.coeffs[i] = mod3((uint8_t) (w.coeffs[i]+sign*v.coeffs[i]));
  65     for (i = 0;i < NTRU_N-1;++i) g.coeffs[i] = g.coeffs[i+1];
  66     g.coeffs[NTRU_N-1] = 0;
  67   }
  68
  69   sign = f.coeffs[0];
  70   for (i = 0;i < NTRU_N-1;++i) r->coeffs[i] = mod3((uint8_t) (sign*v.coeffs[NTRU_N-2-i]));
  71   r->coeffs[NTRU_N-1] = 0;
  72 }
  73 #endif
  74
  75 void
  76 testBug (void)
  77 {
  78 }
  79