ed25519/amd64-64-24k/index_heap.c

   1 #include "sc25519.h"
   2 #include "index_heap.h"
   3
   4 /* caller's responsibility to ensure hlen>=3 */
   5 void heap_init(unsigned long long *h, unsigned long long hlen, sc25519 *scalars)
   6 {
   7   h[0] = 0;
   8   unsigned long long i=1;
   9   while(i<hlen)
  10     heap_push(h, &i, i, scalars);
  11 }
  12
  13 void heap_extend(unsigned long long *h, unsigned long long oldlen, unsigned long long newlen, sc25519 *scalars)
  14 {
  15   unsigned long long i=oldlen;
  16   while(i<newlen)
  17     heap_push(h, &i, i, scalars);
  18 }
  19
  20
  21 void heap_push(unsigned long long *h, unsigned long long *hlen, unsigned long long elem, sc25519 *scalars)
  22 {
  23   /* Move up towards the root */
  24   /* XXX: Check size of hlen, whether cast to signed value is ok */
  25   signed long long pos = *hlen;
  26   signed long long ppos = (pos-1)/2;
  27   unsigned long long t;
  28   h[*hlen] = elem;
  29   while(pos > 0)
  30   {
  31     /* if(sc25519_lt_vartime(&scalars[h[ppos]], &scalars[h[pos]])) */
  32     if(sc25519_lt(&scalars[h[ppos]], &scalars[h[pos]]))
  33     {
  34       t = h[ppos];
  35       h[ppos] = h[pos];
  36       h[pos] = t;
  37       pos = ppos;
  38       ppos = (pos-1)/2;
  39     }
  40     else break;
  41   }
  42   (*hlen)++;
  43 }
  44
  45 /* Put the largest value in the heap in max1, the second largest in max2 */
  46 void heap_get2max(unsigned long long *h, unsigned long long *max1, unsigned long long *max2, sc25519 *scalars)
  47 {
  48   *max1 = h[0];
  49   *max2 = h[1];
  50   if(sc25519_lt(&scalars[h[1]],&scalars[h[2]]))
  51     *max2 = h[2];
  52 }
  53
  54 /* After the root has been replaced, restore heap property */
  55 /* extern void heap_rootreplaced(unsigned long long *h, unsigned long long hlen, sc25519 *scalars);
  56 */
  57 /* extern void heap_rootreplaced_shortscalars(unsigned long long *h, unsigned long long hlen, sc25519 *scalars);
  58 */