/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

#include <stdio.h>
#include <assert.h>

#include "BitString.h"

/*----------------------------------------*/

void
printBitString (BitString bs) {
  int i = LEN_BITSTRING;
  int blank = 0;
  while (i > 0) {
    if (blank) printf(" ");
    --i;
    printf ("%c", (char)(((bs >> i) & 0x1) + '0'));
    blank = i % 8 == 0;
  }
}

void
printPrefix(Prefix p, Mask m) {
  int i = LEN_BITSTRING;
  int blank = 0;
  while ((singleton(i - 1) & m) == 0) {
    if (blank) printf(" ");
    --i;
    printf ("%c", (char)(((p >> i) & 0x1) + '0'));
    blank = i % 8 == 0;
  }
}

/*----------------------------------------*/

Mask zeroPrefix(BitString bs) {
  int i = 1;
  while (i < LEN_BITSTRING) {
    bs = bs | (bs >> i);
    i *= 2;
  }
  return bs ^ (bs >> 1);
}

/* optimization: loop unrolling (here for 64-bit architecture)*/
Mask zeroPrefixFast(BitString bs) {
  register BitString bs1 = bs;

  bs1 |= bs1 >>  1;
  bs1 |= bs1 >>  2;
  bs1 |= bs1 >>  4;
  bs1 |= bs1 >>  8;
  bs1 |= bs1 >> 16;
  bs1 |= bs1 >> 32;

  return bs1 ^ (bs1 >> 1);
}

Mask commonPrefixMask(BitString bs1, BitString bs2) {
  return
    zeroPrefixFast(bs1 ^ bs2);
}

Prefix getPrefix(BitString bs, Mask m) {
  assert(invMask(m));
  return
    bs & (~(m - 1) ^ m);
}

int matchPrefix(BitString bs, Prefix p, Mask m) {
  return
    getPrefix(bs, m) == p;
}