Comparison of Bit Array Implementations using C and Ada

 

I found the following programming example in Bit Array in C - Sanfoundry

#include <stdio.h> #define SIZE (58) /* amount of bits */ #define ARRAY_SIZE(x) (x/8+(!!(x%8))) char get_bit(char *array, int index); void toggle_bit(char *array, int index); void toggle_bit(char *array, int index) {     array[index / 8] ^= 1 << (index % 8); } char get_bit(char *array, int index) {     return 1 & (array[index / 8] >> (index % 8)); } int main(void) {     /* initialize empty array with the right size */     char x[ARRAY_SIZE(SIZE)] = { 0 };     int i;     for (i = 0; i < SIZE; i += 2)         toggle_bit(x, i);     toggle_bit(x, 56);     for (i = 0; i < SIZE; i++)         printf("%d: %d\n", i, get_bit(x, i));     return 0; }

 

The program creates a bit array containing 58 elements. The program works as expected and manages to illustrate very arcane features of the C programming language.

I challenge anybody not familiar with C bit shifting to completely understand how the two void functions named get_bit and toggle_bit actually work.

void toggle_bit(char *array, int index) {     array[index / 8] ^= 1 << (index % 8); } char get_bit(char *array, int index) {     return 1 & (array[index / 8] >> (index % 8)); }

These functions are examples of the “simplicity” of C programming. While the syntax is compact the semantics of these functions are not. Describing what these two functions do would take several paragraphs of text.

 

As an avid Ada programmer I decided to implement a bit array in Ada and perform the same behaviors on the bit array.

The Ada program is slightly longer, sacrificing compactness for clarity.

-- Ada program to implement a bit array with Ada.Text_IO; use Ada.Text_IO; procedure Main is    type bit is range 0 .. 1;    type index is range 0 .. 57;    type bit_array is array (index) of bit with       Component_Size => 1;    x   : bit_array := (others => 0);    Idx : index     := 0; begin    for I in x'Range loop       if I mod 2 = 0 then          toggle_bit (x, I);       end if;    end loop;    toggle_bit (x, 56);    for I in x'Range loop       Put_Line (I'Image & ":" & bit'Image (x (I)));    end loop;    Put_Line("Size of bit array is" & Integer'Image(X'Size) & " bits.");    Put_Line("Length of array is" & Integer'Image(X'Length)); end Main;

 

The Ada programming language measures the size of data types in units of bits while the C program must convert bytes to bits in determining its size.

Compare the corresponding Ada and C code sections:

C:

#define SIZE (58) /* amount of bits */ #define ARRAY_SIZE(x) (x/8+(!!(x%8))) . . . char x[ARRAY_SIZE(SIZE)] = { 0 };

 

Ada:

type bit is range 0 .. 1;    type index is range 0 .. 57;    type bit_array is array (index) of bit with       Component_Size => 1; . . . x   : bit_array := (others => 0);

 

The Ada code defines an integral type named bit with 0 and 1 as the only valid values. The Ada code then defines an index range to be used in the array type. Knowing the index range prevents buffer overflows in other parts of the program.

The array type bit_array is declared. C provides no means to define array types, only array instances.

In the C example the array named x is defined as an array of type char, but we are not interested in values of type char. We are interested in the bit values within each char element. The size of the char array must be declared to be the number of char elements needed to store 58 bits. Each char element is 8 bits, therefore 8 char elements are needed to store 58 bits.

The corresponding Ada source code is somewhat more readable. A bit_array is an array of 58 elements indexed by the values 0 through 57. The size of each array component is 1, which in Ada terms is 1 bit.

The variable x in the C example is declared to be an array of 8 char data elements. All elements (and all 64 bits) are initialized to 0.

The variable x in the Ada example is declared to be an instance of bit_array, which is declared to be an array of 58 bits. Each element is initialized to 0. Only the 58 bits are initialized to 0.

The C function named toggle_bit is difficult to understand.

void toggle_bit(char *array, int index) {     array[index / 8] ^= 1 << (index % 8); }

 

The purpose of this function is to identify the bit specified by the index parameter and toggle the bit. If the bit is 1 then set it to zero. If the bit is 0 then set it to 1.

The Ada procedure named toggle_bit performs the same behavior with a somewhat more verbose, but also clearer syntax.

procedure toggle_bit (arr : in out bit_array; Idx : index) is    begin       if arr (Idx) = 1 then          arr (Idx) := 0;       else          arr (Idx) := 1;       end if;    end toggle_bit;

 

Note that the bits in the bit array are indexed with the same syntax used to index any other Ada array. No special syntax is needed. The compiler writes all the low level bit shifting for the programmer, eliminating the need for an explicit get_bit procedure as found in the C example. The Ada version clearly states toggle logic. If the current value of the bit indexed by Idx is 1 then assign 0 to that bit, otherwise assign 1 to that bit.

Also note the obscurity of the C syntax for passing an array to a function. The array is not actually passed to the function. The name of the array is passed as a pointer to the first element of the array, thus the parameter used to “pass” the array is a pointer to char rather than an array. A pointer to char may be a pointer to the first element of an array of char or it may be a pointer to a char which is not a member of an array of char. C requires the programmer to know whether or not the parameter points to an array. The C syntax also does not specify whether or not the actual parameter passed to this function may be modified by the function.

The Ada procedure specifies the parameter arr is an instance of bit_array. Furthermore, the passing mode “in out” specifies that the value of the array is used and modified by the procedure, specifying that the actual parameter passed to this procedure may be modified by the procedure.

Outputs:

The output of the C program is:

0: 1 1: 0 2: 1 3: 0 4: 1 5: 0 6: 1 7: 0 8: 1 9: 0 10: 1 11: 0 12: 1 13: 0 14: 1 15: 0 16: 1 17: 0 18: 1 19: 0 20: 1 21: 0 22: 1 23: 0 24: 1 25: 0 26: 1 27: 0 28: 1 29: 0 30: 1 31: 0 32: 1 33: 0 34: 1 35: 0 36: 1 37: 0 38: 1 39: 0 40: 1 41: 0 42: 1 43: 0 44: 1 45: 0 46: 1 47: 0 48: 1 49: 0 50: 1 51: 0 52: 1 53: 0 54: 1 55: 0 56: 0 57: 0

 

The output of the Ada program is:

0: 1  1: 0  2: 1  3: 0  4: 1  5: 0  6: 1  7: 0  8: 1  9: 0  10: 1  11: 0  12: 1  13: 0  14: 1  15: 0  16: 1  17: 0  18: 1  19: 0  20: 1  21: 0  22: 1  23: 0  24: 1  25: 0  26: 1  27: 0  28: 1  29: 0  30: 1  31: 0  32: 1  33: 0  34: 1  35: 0  36: 1  37: 0  38: 1  39: 0  40: 1  41: 0  42: 1  43: 0  44: 1  45: 0  46: 1  47: 0  48: 1  49: 0  50: 1  51: 0  52: 1  53: 0  54: 1  55: 0  56: 0  57: 0 Size of bit array is 64 bits. Length of array is 58