[krbdev.mit.edu #2409] util_ordering.c bug - wraparound not correct

[Wyllys Ingersoll via RT]

I think the logic in g_order_check is incorrect, or
at the very least - very convoluted and hard to read.

Nico and I looked at this and came up with a possible
solution.

Below is an updated g_order_check routine for consideration.

-Wyllys


gss_int32
g_order_check(void **vqueue, gssint_uint64 seqnum)
{
    queue *q;
    int i;
    gssint_uint64 expected;

    q = (queue *) (*vqueue);

    if (!q->do_replay && !q->do_sequence)
       return(GSS_S_COMPLETE);

    /* All checks are done relative to the initial sequence number, to
         avoid (or at least put off) the pain of wrapping.        */

    /* wraparound case */
    if (seqnum < q->firstnum) {
         /* if 32 bit, put seqnum into 64 bit range */
         if (q->mask != ~(gssint_uint64)0) {
                 seqnum |= 0x100000000ULL;
                 seqnum -= q->firstnum;
         } else {
                 /*
                  * 64 bit wraparound, just add the number of
                  * elements before the wraparound point
                  * to get the normalized seqnum.
                  */
                 seqnum += (~(gssint_uint64)0) - q->firstnum;
         }
    } else {
         /*
          * Normally (as long as seqnum >= firstnum), just subtract
          * the firstnum to get the relative 'seqnum'.
          */
         seqnum -= q->firstnum;
    }

    /* rule 1: expected sequence number */

    expected = (QELEM(q,q->start+q->length-1)+1) & q->mask;
    if (seqnum == expected) {
         queue_insert(q, q->start+q->length-1, seqnum);
         return(GSS_S_COMPLETE);
    }

    /* rule 2: > expected sequence number */

    if ((seqnum > expected)) {
         queue_insert(q, q->start+q->length-1, seqnum);
         if (q->do_replay && !q->do_sequence)
          return(GSS_S_COMPLETE);
         else
          return(GSS_S_GAP_TOKEN);
    }

    /* rule 3: seqnum < seqnum(first) */
    if (seqnum < QELEM(q,q->start)) {
       if (q->do_replay)
             return(GSS_S_OLD_TOKEN);
       else
             return(GSS_S_UNSEQ_TOKEN);
    }

    /* rule 4+5: seqnum in [seqnum(first),seqnum(last)]  */

    else {
       if (seqnum == QELEM(q,q->start+q->length-1))
          return(GSS_S_DUPLICATE_TOKEN);

       for (i=q->start; i<q->start+q->length-1; i++) {
          if (seqnum == QELEM(q,i))
             return(GSS_S_DUPLICATE_TOKEN);
          if ((seqnum > QELEM(q,i)) && (seqnum < QELEM(q,i+1))) {
             queue_insert(q, i, seqnum);
             if (q->do_replay && !q->do_sequence)
                return(GSS_S_COMPLETE);
             else
                return(GSS_S_UNSEQ_TOKEN);
          }
       }
    }

    /* this should never happen */
    return(GSS_S_FAILURE);
}