stride.cpp

bool NStrideDetector::IsMergable(int64_t ea, int32_t /*size*/, const TRAINING& t) const
{
  //
  // Note: be careful of the sign for % operation
  // 
  int64_t abs_stride = (t.distance > 0 ? t.distance : -t.distance);
  int64_t lb = (t.low  - abs_stride < t.low  ? t.low  - abs_stride : t.low/*0*/);
  int64_t ub = (t.high + abs_stride > t.high ? t.high + abs_stride : t.high/*-1*/);
 
  if (/*(t.size == size) &&*/ (((t.low - ea) % abs_stride) == 0) &&
    (lb <= ea && ea <= ub))
    return true;
  else
    return false;
}
 
 
 
/*
  
 eStart --> eFirstAddrSeen --> eStrideLearned --> eWeakStride --> eStrongStride
 
*/
 
NStrideDetector::StrideAction NStrideDetector::QueryAndTrainWorker(int64_t ea,
  int32_t size, NStrideDetector::TRAINING& t)
{
  switch (t.state)
  {
  case eStart:
    // First: see the first address
    t.state  = eFirstAddrSeen;
    t.low    = ea;
    t.high   = 0;
    t.distance = 0;
    t.size   = size;
 
#ifdef STRIDE_PROFILING
    t.cur_stride_length = 0;
#endif
    return actionPoint; // Point
 
  case eFirstAddrSeen:
    // Second: see the second address, learning the stride
    t.state  = eStrideLearned;
    t.distance = (ea - t.low);
 
    if (t.low < ea)
    {
      // Increasing stride
      t.high = ea;
    }
    else /* if (stride->low >= ea) */
    {
      // Decreasing stride: make it sure 'low' and 'high'
      t.high = t.low;
      t.low  = ea;
    }
    if (t.distance == 0)
      return actionFixedPoint;
    else
      return actionPoint; // It's still treated as a point
 
  case eStrideLearned:
    if (t.distance == 0 && ea == t.low)
    {
      // Zero stride: remain on the state
      return actionFixedPoint; // Fixed location
    }
    else if (t.distance == 0 && ea != t.low)
    {
      // Zero stride was broken: let's learn this stride
      t.low    = std::min(t.low,  ea);
      t.high   = std::max(t.high, ea);
      t.size   = size;
      t.distance = (ea - t.low);
      return actionPoint;
    }
    else if (IsMergable(ea, size, t))
    {
      // Let's start a new stride
      t.state = eWeakStride;
      t.low   = std::min(t.low,  ea);
      t.high  = std::max(t.high, ea);
#ifdef STRIDE_PROFILING
      t.cur_stride_length = 3;
#endif
      return actionNewStride;
    }
    else
    {
      // Non-stride (e.g., 10 -> 20 -> 5): just goto first stage
      t.state  = eFirstAddrSeen;
      t.low    = ea;
      t.high   = 0;
      t.distance = 0;
      t.size   = size;
#ifdef STRIDE_PROFILING
      t.cur_stride_length = 0;
#endif
      return actionPoint;
    }
 
  case eWeakStride:
    if (t.IsReset())
    {
      t.low = t.high = ea;
      return actionNewStride;
    }
    else if (IsMergable(ea, size, t))
    {
      t.state = eStrongStride;
 
      if (ea > t.high)
      {
#ifdef STRIDE_PROFILING
        t.cur_stride_length++;
#endif
        t.high = ea;
        return actionStrideHigh;
      }
      else if (ea < t.low)
      {
#ifdef STRIDE_PROFILING
        t.cur_stride_length++;
#endif
        t.low = ea;
        return actionStrideLow;
      }
      else
        return actionStrideSame;
    }
    else
    {
      // Non-stride: backward..
      t.state  = eStrideLearned;
      t.low   = ea;
      t.high  = ea;
#ifdef STRIDE_PROFILING
      update_max(t.max_stride_length, t.cur_stride_length);
      update_min(t.min_stride_length, t.cur_stride_length);
      t.cur_stride_length = 1;
#endif
      return actionPoint;
    }
 
  case eStrongStride:
    if (t.IsReset())
    {
      t.low = t.high = ea;
      return actionNewStride;
    }
    else if (IsMergable(ea, size, t))
    {
      if (ea > t.high)
      {
#ifdef STRIDE_PROFILING
        t.cur_stride_length++;
#endif
        t.high = ea;
        return actionStrideHigh;
      }
      else if (ea < t.low)
      {
#ifdef STRIDE_PROFILING
        t.cur_stride_length++;
#endif
        t.low = ea;
        return actionStrideLow;
      }
      else
        return actionStrideSame;
    }
    else
    {
      // Non-stride: goto weak stride, but don't discard stride
      // And, assume that this address will be the start of the new stride stream
      t.state = eWeakStride;
      t.low   = ea;
      t.high  = ea;
#ifdef STRIDE_PROFILING
      update_max(t.max_stride_length, t.cur_stride_length);
      update_min(t.min_stride_length, t.cur_stride_length);
      t.cur_stride_length = 1;
#endif
      return actionNewStride;
    }
  }
 
  return actionPoint;
}