Po drátě 4: Řešení úlohy č. 13

Zase jednou značně self-referenční úloha. Program na zabezpečení Céčkového zdrojáku proti chybám při přenosu přidáním jakýchsi kontrolních součtů na konce řádků. Ovšem na programu se už vyřádil nějaký šotek a spoustu chyb v něm natropil. Některé zjevné, jiné, jak se brzy ukáže, značně nenápadné.

Úlohu bylo možné řešit zkusmo – měnit podezřelé kousky řádků tak dlouho, než budou kontrolní součty sedět, ale jednak to v těch nejzajímavějších místech jde dost ztuha, jednak jsou překlepy i v kontrolních součtech (jak napovídá třeba přítomnost "n" v jinak poklidně hexadecimálním čísle).

Proto je lepší zamyslet se nad tím, jak kód funguje. Zabezpečuje jednotlivé řádky, ale počítá se 8-bitovýmy xory, takže chrání zvlášť všechny nulté bity bajtů, zvlášť všechny první atd. Uvažujme o něm tedy jako o kódu, který doplní 57 datových bitů o 6 kontrolních, spočítaných následovně: Očíslujeme si oněch 57 datových bitů 6-bitovými čísly, ve kterých jsou alespoň dvě jedničky (prvních pár bitů tedy dostane čísla 000011, 000101, 000110 a 000111). Potom i-tý z kontrolních bitů nastavíme na xor všech datových bitů, jejichž pořadové číslo má na i-tém místě jedničku.

Všimněte si, že takový kód dokáže opravit libovolnou jednobitovou chybu: Pokud nastane v datové části, překlopí se alespoň dva kontrolní bity (protože jsme používali jen čísla bitů, ve kterých jsou aspoň dvě jedničky) a podle toho, které, ihned poznáme, o který datový bit se jednalo. Pokud naopak nastane chyba v kontrolním bitu, hned víme, že se tak stalo, protože nesedí právě jeden kontrolní bit.

Náš kód je tedy schopen na každé z osmi bitových pozic v bajtu opravit jednu chybu na řádku. Na některých řádcích se tyto chyby soustředily do jediného bajtu, na jiných zase byla každá pozice špatně v jiném znaku. Chyby, které kód neumí opravit, každopádně šotek nenapáchal.

Na dekódování si můžeme napsat třeba následující program:

#include <stdio.h>
#include <string.h>

#define Z 6
#define L ((1<<Z)-Z-1)

int main(int argc, char **argv)
{
  char line[256];
  int checks[7];

  int verb = (argc > 1);

  while (fgets(line, sizeof(line), stdin))
    {
      int l = strlen(line);
      if (l && line[l-1] == '\n')
        l--;
      if (l != L+3+2*Z || memcmp(line+L, "// ", 3))
        {
          fprintf(stderr, "Syntax error: %s\n", line);
          return 1;
        }
      for (int k=0; k<Z; k++)
        sscanf(line+L+3+2*k, "%2x", &checks[k]);
      for (int i=0, j=0; i < (1<<Z); i++)
        if (i & (i-1))
          {
            for (int k=0; k<Z; k++)
              if (i & (1<<k))
                checks[k] ^= line[j];
            j++;
          }
      int e = 0, fixes=0;
      for (int k=0; k<Z; k++)
        e |= checks[k];
      if (e)
        for (int b=1; b<256; b+=b)
          {
            int p = 0;
            for (int k=0; k<Z; k++)
              if (checks[k] & b)
                p |= (1<<k);
            for (int i=0, j=0; i < (1<<Z); i++)
              if (i & (i-1))
                {
                  if (i==p)
                    {
                      line[j] ^= b;
                      fixes++;
                    }
                  j++;
                }
          }
      l = L;
      while (l>0 && line[l-1] == ' ')
        l--;
      line[l] = 0;
      if (verb)
        {
          if (fixes)
            printf("C%d  ", fixes);
          else if (e)
            printf("XX  ");
          else
            printf("..  ");
        }
      puts(line);
    }
  return 0;
}

Opravený zdroják pak vyjde takto (ten šotek je ale potvora!):

/*
 *  An error correction code capable of correcting
 *  single-bit errors.
 *
 *  (c) 2009 SoTec s.r.o.
 */

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

int main(void)
{
  char x[256];
  unsigned char ch[6], pw[6] = { };
  while (fgets(x, sizeof(x), stdin))
    {
      int l = strlen(x);
      if (l && x[l-1] == '\n')
        l--;
      while (l < 57)
        x[l++] = ' ';
      l = 57;
      memset(ch, 0, sizeof(ch));
      for (int i=0, j=0; i < (1<<6); i++)
        if (i & (i-1))
          {
            for (int k=0; k<6; k++)
              if (i & (1<<k))
                ch[k] ^= x[j];
            j++;
          }
      l += sprintf(x+l, "// ");
      for (int k=0; k<6; k++)
        {
          l += sprintf(x+l, "%02x", ch[k]);
          pw[k] -= ch[k];
        }
      puts(x);
    }
  uint32_t speed_of_light = 299780450;
  uint32_t number = 0062660730;
  for (int k=0; k<6; k++) {
    number += pw[k];
  number *= speed_of_light; }
  if (number % 1001 == 997)
    fprintf(stderr, "Password: %08X\n", number);
  else
    fprintf(stderr, "This is not the right file.\n");
  return 0;
}

Komentář

Úlohy, ve kterých je potřeba si program nejdříve opravit, patří k podrátí klasice, ovšem opravovat namísto hloupých programátorských chyb škodolibé zásahy do zdrojáku leží přeci jenom o level výše :-)

Způsob kódování jsme úmyslně vybrali jednoduchý (kdo se už s teorií samoopravných kódů někdy potkal, jistě poznal Hammingův kód), i tak se s ním dá užít spousta legrace bez přemíry matematiky.

Menší oříšek představovalo zabudování kontroly konsistence hesla do programu – pokud přidáte kontrolu, samozřejmě se změní kontrolní součty a tím i heslo, takže musíte upravit kontrolu, tím se změní heslo, a tak dále. Jak z toho ven?

Úlohu s vydatnou pomocí všech šotků z okolí napsal a opravil Martin Mareš.