Technika: Bitove operace

TECHNIKA: BITOVÉ OPERACE

Přiřazením V="A" je do proměnné V uložen znak "A". O tom se můžeme jednoduše přesvědčit příkazem say V. V počítači je hodnota "A" uložena do jednoho bytu jako bitový řetězec. Uvidíme ho příkazem say X2B(C2X(V)). Přitom samotný příkaz say C2X(V) zobrazí hexadecimální reprezentaci znaku "A". Funkce C2D(V) vrátí hodnotu V interpretovanou jako desítkové číslo. V ASCII má "A" hodnotu, zapsáno hexadecimálně, 41. Tj. v desítkové reprezentaci 4*16+1=65.

Seznam implementací bitových operací

AND

Funkce BITAND vrací bitový součin operandů.

OR

Funkce BITOR vrací bitový součet operandů.

XOR

Funkce BITXOR vrací výsledek operace eXclusive OR (XOR) prováděné po bitech.

Posun vlevo

Posun operandu N o B bitů doleva se provede pomocí výrazu
D2C(C2D(N)*(2**B))
B musí být nezáporné celé číslo.

Posun vpravo

Posun operandu N o B bitů doprava se provede pomocí výrazu
D2C(C2D(N)%(2**B))
B musí být nezáporné celé číslo.

PŘÍKLAD 1 - Vernamova metoda
BITXOR funkce je vlastně slavná Vernamova metoda šifrování a dešifrování dat. Chceme-li zašifrovat zprávu Text, vytvoříme nejdříve náhodný řetězec bitů Klic stejné délky jako je zpráva. Pak Text zašifrujeme příkazem

Sifra=BITXOR(Text,Klic)

Dešifrování provedeme příkazem

Puvodni_text=BITXOR(Sifra,Klic)

Pak Text==Puvodni_Text. Zkuste následující program.

/* VERNAM */
parse arg Text
L = LENGTH(Text) * 8; Key = ""
do J = 1 to L
  Key = Key || RANDOM(0, 1)
end
Key = X2C(B2X(Key))
Ciphertext = BITXOR(Text, Key)
Plaintext  = BITXOR(Ciphertext, Key)
if Plaintext == Text
  then say "Vernamova metoda pracuje"
  else say "Eh?"

PŘÍKLAD 2 - Gray code
Grayův kód (podle autora Franka Graye) je celočíselnou funkcí G(I), která je bijekcí pro každé celé číslo

N>=0, 0<=I<=2**(N-1)
a má vlastnost: Binární reprezentace G(I) a G(Ip1), pro Ip1=I+1, se liší pouze v jediném bitu.
Algoritmus generující Grayův kód využívá operace exclusive or (BITXOR) operandů I a I%2 (celá část po dělení I/2), což je bitový posun doprava o jeden bit.
Program GRAY zobrazí, pro hodnotu vstupního argumentu 15
00000000 00000001 00000011 00000010 00000110 00000111 00000101 00000100 00001100 00001101 00001111 00001110 00001010 00001011 00001001 00001000

Pro výpočet potřebujeme znát počet bitů kódu zaokrouhlený nahoru na hranici bytu. Zjistíme tedy počet bitů nutných k zápisu čísla N pomocí
LENGTH(X2B(D2X(N)))
Funkce BYTES vrací potřebný počet bytů pro zadaný počet bitů.

/* GRAY_CODE */
parse arg N
S = BYTES(LENGTH(X2B(D2X(N))))
Gray_code = ""
do I = 0 to N
  Ibrs1 = I % 2
  A = D2C(I, S); B = D2C(Ibrs1, S)
  C = BITXOR(A, B)
  Gray_code = Gray_code X2B(C2X(C))
end
say Gray_code
exit

BYTES: procedure
parse arg B
R = B // 8
if R <> 0 then B = B + 8 - R
return B % 8

PŘÍKLAD 3 - Dekompresní funkce

Vstupem pro tuto funkci je kompresovaný text C. Obsahuje dva typy kódových slov (příkazů) - LITERAL X and COPY X,-Y.

LITERAL X
znamená: připoj beze změny následujících X znaků v kompresovaném textu C na konec dekompresovaného textu D.

COPY X,-Y
znamená: vrať se zpět v D o Y znaků a zkopíruj X následujících znaků na konec D.
Pro kódování příkazu LITERAL použijeme 8 bitů a pro kódování příkazu COPY 16 bitů. Pokud v dalším příkazu jsou první 4 bity nulové, pak je to LITERAL a další 4 bity určují jeho délku X v intervalu 1 až 16 (ale kóduje se 0 až 15). Následujících X znaků je literál.
Jinak jde o příkaz COPY. V prvních 4 bitech je délka X. Ta může být 3 až 17, ale kóduje se 1 až 15. V dalších 12-ti bitech je posunutí Y, hodnota 1 až 4096, ale kóduje se 0 až 4095.
Tak třeba vstupní řetězec AAAAAABBBBCCCAABBBBC s 20-ti znaky může být kompresován na řetězec

'00'X || "A" ||,     /* literal */
'3000'X || ,         /* copy    */
'00'X || "B" || ,    /* literal */
'1000'X || ,         /* copy    */
'02'X || "CCC" || ,  /* literal */
'5008'X

s 14-ti znaky.

DECOMPRESS: procedure
parse arg C
D = ""; LengthC = LENGTH(C); Pc = 1; Pd = 1
do while Pc < LengthC
  Byte = SUBSTR(C, Pc, 1)
  if BITOR(Byte, '0F'X) = '0F'X
  then call LITERAL Byte
  else call COPY Byte
end
return D

LITERAL: procedure expose C D Pc Pd
parse arg L
L = C2D(L) + 1
D = D || SUBSTR(C, Pc + 1, L)
Pc = Pc + L + 1
Pd = Pd + L
return

COPY: procedure expose C D Pc Pd
parse arg L
L1 = C2D(L) % 16 + 2; L = L1
X = C2D(BITAND('0FFF'X, SUBSTR(C, Pc, 2))) + 1
Y = Pd - X
do while L > X
  D = D || SUBSTR(D, Y, X)
  L = L - X
  X = 2 * X
end
if L > 0 then D = D || SUBSTR(D, Y, L)
Pc = Pc + 2; Pd = Pd + L1
return

Literatura
Fiala E.R., Greene D.H., Data Compression with Finite Windows

CACM, April 1989, Vol. 32, No. 4, pp. 490-505

Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P., Numerical Recipes in C : the art of scientific computing

- 2nd ed. University Press, Cambridge, 1992