Inconsistent Output from Procedure Call within Another Procedure

Question

I've got a problem with inconsistent output from a procedure called from within another procedure. The following is a cut-down version of the relatively simple hashing program.

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Unchecked_Conversion;
with Ada.Strings; use Ada.Strings;

procedure lab5_C_Part_A is

package LongIntIO is new Ada.Text_IO.Integer_IO(Long_Integer);
use LongIntIO;

package IntIO is new Ada.Text_IO.Integer_IO(Integer);
use IntIO;

type String2 is new String(1..2);
type String16 is new String(1..16);

function ConvertChar is
    new Ada.Unchecked_Conversion(Character, Integer);

function ConvertString2 is 
    new Ada.Unchecked_Conversion(String2, Integer);

table: array(1..128) of String16:= (others => "                ");

function hash(key: in String16) return Integer is
A: String2:= String2(key(15..16));
begin
    return ((((ConvertChar(key(1)) + ConvertChar(key(10))) * 512) + ConvertString2(A)) / 256) mod 128;
end hash;

procedure linearProbe(key: in String16; index, probes: out Integer) is 
begin
    probes:= 1;
    index:= hash(key);
    put("inside method linearProbe() : "); put(index); new_line;
    while true loop
        if table(index) = key then put("key found"); new_line; exit;
        elsif table(index) = "                " then put("empty found"); new_line; exit;
        else
            index:= index + 1;
            if index > table'Length then
            index:= 1;
            end if;
        put("incrementing"); new_line;
        end if;
        probes:= probes + 1;
    end loop;
end linearProbe;

index: Integer:= 1;
probes: Integer:= 1;

begin
    put("outside method linearProbe() : "); put(hash("Afterwards      ")); 
    new_line;    
    linearProbe("Afterwards      ", index, probes);
    put("index: "); put(index); new_line;
    put("probes: "); put(probes); new_line;
end;

The output when the program is run multiple times looks like this:

kcg@hardmode-activated:~/ada/lab5 test > gnatmake lab5_C_Part_A
gcc-4.6 -c lab5_C_Part_A.adb
lab5_C_Part_A.adb:5:11: warning: file name does not match unit name, should be "lab5_c_part_a.adb"
lab5_C_Part_A.adb:16:01: warning: types for unchecked conversion have different sizes
lab5_C_Part_A.adb:19:01: warning: types for unchecked conversion have different sizes
gnatbind -x lab5_C_Part_A.ali
gnatlink lab5_C_Part_A.ali
kcg@hardmode-activated:~/ada/lab5 test > ./lab5_C_Part_A
outside method linearProbe() :           8
inside method linearProbe() :           8
empty found
index:           8
probes:           1
kcg@hardmode-activated:~/ada/lab5 test > ./lab5_C_Part_A
outside method linearProbe() :           9
inside method linearProbe() :           8
empty found
index:           8
probes:           1
kcg@hardmode-activated:~/ada/lab5 test > ./lab5_C_Part_A
outside method linearProbe() :           8
inside method linearProbe() :           8
empty found
index:           8
probes:           1
kcg@hardmode-activated:~/ada/lab5 test > ./lab5_C_Part_A
outside method linearProbe() :           9
inside method linearProbe() :           8
empty found
index:           8
probes:           1

I'd love an answer as to why this is happening, but I would be happy if someone could just tell me whether they get the same output as me.

If you need any more information, please let me know.

Answer 1

The purpose of Unchecked_Conversion is to read data that is declared as one type, as if the bits stored in memory were data of a different type. It really is guaranteed to work only when the two types have the same size (RM 13.9(6)).

This case in particular is problematic:

function ConvertString2 is 
    new Ada.Unchecked_Conversion(String2, Integer);

String2 is 16 bits; the size of Integer could vary from one Ada implementation to another, but based on the warnings, it is probably 32 bits on your compiler. The problem is that this Unchecked_Conversion can be implemented simply by taking the address of the data and reading a 32-bit integer at that address. Since the source is only 16 bits, the program would attempt to read data that doesn't belong to the object. The result is likely to be inconsistent, if the extra data is uninitialized or is something on the stack that may depend on what procedures were run previously. (You could also get a program fault if the extra data is actually outside of the memory space allocated to the program. And depending on the processor, doing something like this can lead to an alignment fault if the source is not 4-byte aligned.)

To do this correctly, you should define an integer type that you know is the same size as String2:

type String2_Int is range -(2**(String2'Size-1)) .. 2**(String2'Size-1) - 1;
for String2_Int'Size use String2'Size;

which will be, in effect,

type String2_Int is range -32768 .. 32767;
for String2_Int'Size use 16;

Also, it's best to specify the alignment of the String2:

for String2'Alignment use 16;

in case you're running on a processor that requires 16-bit integer reads to be on 2-byte boundaries. Now:

function ConvertString2 is 
    new Ada.Unchecked_Conversion(String2, String2_Int);

and if you want to produce an Integer, you first use the above to convert to a String2_Int, and then use a normal type conversion (not an Unchecked_Conversion) to convert the String2_Int to an Integer.

You could do the same kind of transformation here:

function ConvertChar is
    new Ada.Unchecked_Conversion(Character, Integer);

but there's no need, since Character'Pos(c) will give you what you want, probably (it returns a result in the range 0 .. 255; if you want something in the -128 .. 127 range, then an unchecked conversion to a signed 8-bit type would work, or you could just do the math yourself). You could also forgo the Unchecked_Conversion on String2, and just use Character'Pos on each of the two characters and combine the results like

256 * Character'Pos(S(1)) + Character'Pos(S(2))

or something along those lines.