The three main loops in HAVEGE


HAVEGE consists mainly in three while  loops which body consists in an unrolled larger loop.
This unrolling is done in order to allow to exercise more volatile hardware states:
essentially the branch predictor and the instruction cache.

The unrolling also allows to personalized each of the iterations in the code with different constants, but also operations (done for MyHAVEGE)



The first  initialization loop ( initHAVEGE1):
 
while (..){
..
     if (Walk[K] > 0) X++;
     Walk[K] = ((Walk[K] >> 5) ^ (Walk[K] << 27)) ^ HardClock () ^
     (Walk[(K + STEP) & ((CACHESIZE<<1) - STEP)] >> 31);
      K = (K + step) & ((CACHESIZE<<1) - STEP);
..
}
The purpose of this initialization phase is to collect uncertainty from the instruction cache and the branch predictor.
Walk is a table twice as large as the data cache.
 
Normal state long after the last OS interrupt:
- I-cache holds the complete  while body
- branch target prediction information is valid and correct
- branch direction prediction information is erratic, but corresponds to the last occurences in this loop

OS interrupts destroy (part of) this state.
 
 



The second initialization loop  (initHAVEGE2):
while (..){
..
if (pt & andpt) /* andpt is simply a constant*/
  {
   PT2 = PT2 ^  0x3333;
  }
PT=pt & ANDPT; /* part of pt is used as a pointer in a table twice as large as the data cache*/
pt= Walk[PT];
PT2=Walk[(PT2 & ANDPT2) ^ ((PT ^ XORPT) & XORPT)];
/* part of PT2 is also used as a pointer*/
              if (pt & Andpt)
  {
   PT2 = PT2 ^ 0x3333;
  }
Inter = HardClock();
T= ((T<< 11) ^ (T>> 21))) ^ Inter ;
pt = pt ^ T;
Walk[PT]= pt;
..
}
 
The purpose of this  second initialization phase is first to set the self-modifying walk in an unpredictable initial state, second to continue to gather uncertainty from the instruction cache,   the branch predictor and the data cache.

Normal state long after the last OS interrupt:
- half of the table is present in the L1 cache
- I-cache holds the complete  while body
- branch target prediction information is valid and correct
- branch direction prediction information is erratic, but corresponds to the last occurences in this loop

OS interrupts destroy (part of) this state.
 
 
 


The "production" loop  (WalkHAVEGE):
while (..){
..
if (pt & andpt)
  {
   PT2 = PT2 ^  0x3333;
  }
PT=pt & ANDPT;
pt= Walk[PT];
PT2=Walk[(PT2 & ANDPT2) ^ ((PT ^ XORPT) & XORPT)];
RESULT[i]= pt ^ PT2 ^ 0x3333;
if (pt & Andpt)
  {
   PT2 = PT2 ^ 0x3333;
  }
Inter = HardClock();
T= ((T<< 11) ^ (T>> 21))) ^ Inter ;
pt = pt ^ T;
Walk[PT]= pt;
i++;
..
}
 
A random number  word is produced on each iteration. Moreover uncertainty is continuously gathered from the instruction cache, the branch predictor and the data cache (just as the previous loop).