Technique: Bitwise operations
After interpretation of the statement V="A" we can see the contents of the V variable by the simple statement say V. It displays A on the screen. The value "A" is saved in one byte as a sequence bits. We display this sequence by the Rexx say X2B(C2X(V)) statement. The statement say C2X(V) will show the hexadecimal representation. And the C2D(V) function returns the value of V interpreted as a decimal number, for our example and ASCII it is 65 (16*4+1).
List of implementations of bitwise operations
AND
The BITAND function is bitwise AND operation, it returns its operators ANDed together bit by bit.
OR
The BITOR function is bitwise OR operation, it returns its operators ORed together bit by bit.
XOR
The BITXOR function is bitwise eXclusive OR (XOR) operation, it returns its operators XORed together bit by bit.
LEFT SHIFT
Bitwise left shift by B bits for N is equal
D2C(C2D(N)*(2**B))
B must be nonnegative.
RIGHT SHIFT
Bitwise rigth shift by B bits for N is equal
D2C(C2D(N)%(2**B))
B must be nonnegative.
EXAMPLE 1 - Vernam's method
The BITXOR function is as well the famous Vernam's encryption and decryption method. To encrypt a message Text, using Vernam's method, proceed as follows. First, create random string of bits Key, where LENGTH(Text)=LENGTH(Key). Then encrypt the Text by
Ciphertext=BITXOR(Text,Key)
To decrypt the ciphertext perform
Plaintext=BITXOR(Ciphertext,Key)
Then Text==Plaintext. You can try the following 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 "Vernam's method works"
else say "Eh?"
|
EXAMPLE 2 - Gray code
Gray code is a function G of the integers I, that for each integer N>=0 is one-to-one for
0<=I<=2**(N-1)
and that has the following property: The binary representation of
G(I) and
G(Ip1), for
Ip1=I+1, differ in exactly one bit.
The algorithm for generating this code is simply to form the bitwise exclusive-or (BITXOR) of I and I%2, where I%2 is bitwise right shift by 1 bit.
The following program GRAY displays on the screen, for the argument equals 15
00000000 00000001 00000011 00000010 00000110 00000111 00000101 00000100 00001100 00001101 00001111 00001110 00001010 00001011 00001001 00001000
We need to know the number of bits necessary to represent the codes plus the padding to align to nearest byte boundary. The number of bits of the N-th code is
LENGTH(X2B(D2X(N)))
The BYTES function returns the necessary number of bytes for a given number of bits.
/* 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
|
EXAMPLE 3 - Decompression routine
The input for this routine is a compressed text C. It contains two types codewords - LITERAL X and COPY X, -Y.
LITERAL X
means pass the next X characters directly into the uncompressed output D.
COPY X,-Y
means go back
Y characters in the uncompressed output and copy
X characters forward to the current position.
We will use 8 bits for coding a LITERAL codeword and 16 bits for coding a COPY codeword. If the first 4 bits are 0, then the codeword is a literal; the next 4 bits encode the length X in the range 1 to 16 (0 to 15 in code) and the following X characters are literal. Otherwise, the codeword is a copy; the first 4 bits encode a length X in range 3 to 17 (1 to 16 in code) and the next 12 bits are a displacement Y in the range 1 to 4096 (0 to 4095 in code).
The input string AAAAAABBBBCCCAABBBBC with 20 characters can be compressed into the string
'00'X || "A" ||, /* literal */
'3000'X || , /* copy */
'00'X || "B" || , /* literal */
'1000'X || , /* copy */
'02'X || "CCC" || , /* literal */
'5008'X
with 14 characters.
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
|
Literature
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
