Examen intermédiaire

La méthode compress peut être écrite de nombreuses manières différentes.

La solution retenue ci-dessous consiste à toujours travailler sur le bit de poids faible du masque (mask) et de la valeur à compresser (i). À chaque itération, si le bit de poids faible de mask vaut 1, alors le bit de poids faible de i est placé à la bonne position du résultat, position mémorisée dans la variable shift. Cela fait, les deux valeurs sont décalées d'une position sur la droite, ce qui élimine le bit traité à l'instant et place le prochain à traiter dans le bit de poids le plus faible.

Avec cette solution, dès que le dernier bit valant 1 de mask a été traité, mask vaut 0 et la boucle peut être arrêtée. (Pour que cela fonctionne, il faut bien entendu utiliser le décalage à droite logique, donc l'opérateur >>>, pour décaler mask, faute de quoi la boucle ne s'arrête jamais lorsque le bit de poids fort de mask vaut 1.)

public static int compress(int i, int mask) {
  int result = 0;
  int shift = 0;
  while (mask != 0) {
    if ((mask & 1) == 1) {
      result |= (i & 1) << shift;
      shift += 1;
    }
    i >>>= 1;                   // ou i >>= 1
    mask >>>= 1;
  }
  return result;
}

Les propriétés suivantes sont vraies :

• compress(i, m) == compress(i & m, m), car les bits de i pour lesquels le bit de m correspondant vaut 0 ne font pas partie du résultat, et donc le fait de les masquer — avec i & m — n'a aucun effet sur ce dernier,
• compress(i, -1) == i, car -1 est une valeur dont tous les bits valent 1, donc aucun bit de i n'est éliminé,
• compress(i, 1 << n) == (i >> n) & 1, car 1 << n est une expression dont seul le bit d'index n vaut 1, et ce bit de i est donc extrait et placé dans le bit de poids faible du résultat, ce qui est équivalent à décaler i de n positions vers la droite puis ne garder que le bit de poids faible.

Les deux autres propriétés sont fausses :

• compress(i, i) == i (contre-exemple : compress(2, 2), qui vaut 1),
• compress(i, -1 << n) == i >> n (contre-exemple : compress(-1, -1 << 31), qui vaut 1 alors que -1 >> 31 vaut -1).

Vu l'ordre des groupes des bits avant démêlage, trois appels à compress sont nécessaires :

• un pour extraire les groupes A et B, qui sont déjà dans le bon ordre,
• un pour extraire le groupe C,
• un pour extraire le groupe D.

Les masques à utiliser sont très facile à noter en binaire, sachant que seuls les bits à extraire doivent valoir 1.

Une fois les trois extractions effectuées, il ne reste plus qu'à combiner les trois groupes au moyen de décalages et de « ou » bit à bit. On obtient donc :

int untangle(int tangled) {
  int ab = compress(tangled, 0b010101_101010);
  int c_ = compress(tangled, 0b101010_000000);
  int d_ = compress(tangled, 0b000000_010101);
  return (d_ << 9) | (ab << 3) | c_;
}

(Les noms des variables c_ et d_ ont été choisis afin que les masques soient alignés, ce qui permet de facilement vérifier que chaque bit n'est à 1 que dans exactement un des trois masques.)

La table des syndromes est une table associant l'index d'un bit — compris entre 0 et 112 (exclu) — à son syndrome — une valeur de 24 bits. On peut donc la représenter au moyen d'une table associative dont les clefs et les valeurs sont des entiers de type Integer.

// Note : l'attribut "final" n'est pas obligatoire
private final Map<Integer, Integer> syndromeTable;

Pour inverser un bit, il faut déterminer l'index de l'octet du tableau qui le contient, puis l'index du bit dans cet octet.

Cela peut se faire au moyen de la division entière par Byte.SIZE — qui vaut 8, le nombre de bits dans un octet — et de son reste. Le quotient donne l'index de l'octet, tandis que le reste donne la position du bit mais depuis la gauche, et pas depuis la droite comme habituellement.

En tenant compte de cela, on peut calculer un masque dont le seul bit à 1 est celui à inverser, et utiliser un « ou exclusif » bit à bit afin de faire l'inversion.

public static void flipBit(byte[] bytes, int bitIndex) {
  int mask = 1 << (Byte.SIZE - 1 - (bitIndex % Byte.SIZE));
  bytes[bitIndex / Byte.SIZE] ^= mask;
}

On peut aussi tirer parti du fait que Byte.SIZE vaut 8, et est donc une puissance de deux, pour calculer la division et son reste au moyen d'opérations bit à bit :

public static void flipBit(byte[] bytes, int bitIndex) {
  int mask = 1 << (7 - (bitIndex & 7));
  bytes[bitIndex >> 3] ^= mask;
}

Le calcul de la table des syndromes se fait en itérant sur toutes les positions des bits d'un message, qui vont de 0 à 112 (exclu), en calculant le syndrome du bit à cette position et en l'insérant dans la table.

Comme dit dans l'énoncé, le syndrome se calcule en déterminant le CRC24 d'un tableau de 112 bits (14 octets) dont seul le bit dont le syndrome est à calculer vaut 1. Les tableaux Java étant initialisés avec des 0, un simple appel à flipBit sur un tableau nouvellement créé suffit à obtenir ce tableau.

Le constructeur s'écrit donc ainsi :

public OneBitErrorDetector(Crc24 crc24) {
  Map<Integer, Integer> syndromeTable = new HashMap<>();
  for (int bitI = 0; bitI < MESSAGE_BITS; bitI += 1) {
    byte[] message = new byte[MESSAGE_BITS / Byte.SIZE];
    flipBit(message, bitI);
    syndromeTable.put(crc24.crc(message), bitI);
  }
  // Note : l'utilisation de unmodifiableMap est optionnelle
  this.syndromeTable = unmodifiableMap(syndromeTable);
}

en faisant l'hypothèse que la constante suivante a été déclarée :

private static final int MESSAGE_BITS = 112;

La méthode indexOfBitToFlip s'écrit très facilement au moyen de getOrDefault, puisqu'elle doit retourner la clef associée au CRC reçu en argument, ou -1 si celui-ci ne correspond à aucun syndrome.

public int indexOfBitToFlip(int messageCrc) {
  return syndromeTable.getOrDefault(messageCrc, -1);
}

La manière la plus simple d'écrire la méthode stuff consiste à accumuler dans une liste séparée les octets du prochain bloc, comme suggéré dans l'énoncé. Cette liste se nomme currentBlock ci-dessous.

Seuls les octets non nuls sont accumulés dans ce bloc, étant donné que les octets nuls ne figurent pas dans la version transformée de la séquence. Dès que l'octet courant est nul, ou que 254 octets non nuls ont été accumulés dans le bloc courant, celui-ci est terminé et la séquence correspondante peut donc être écrite dans le résultat. Indépendemment du type de bloc, l'en-tête est toujours égal au nombre d'octets (non nuls) du bloc, plus un. On écrit donc cette valeur dans la séquence transformée, suivie du contenu du bloc.

Une fois la totalité des octets de la séquence à transformer traités, il faut encore penser à traiter le dernier bloc. Sachant que la séquence à transformer a été — conceptuellement en tout cas — augmentée d'un octet nul, le traitement du dernier bloc se fait comme celui d'un bloc terminé d'un octet nul.

public static List<Byte> stuff(List<Byte> bytes) {
  List<Byte> stuffed = new ArrayList<>();

  List<Byte> currentBlock = new ArrayList<>();
  for (byte b : bytes) {
    if (b != 0) currentBlock.add(b);
    if (b == 0 || currentBlock.size() == 254) {
      stuffed.add((byte) (currentBlock.size() + 1));
      stuffed.addAll(currentBlock);
      currentBlock.clear();
    }
  }
  stuffed.add((byte) (currentBlock.size() + 1));
  stuffed.addAll(currentBlock);

  return stuffed;
}