I want to prove the correctness of some of my programs, but I do not know where to start. Let's say I have the following program, how can I prove its correctness or disadvantage. How can I go from the source below and connect them to theoretical progress. Coq or ACL2 or just about anything.
The code below just counts the bytes that it reads from standard input. It has 2 versions, one byte by byte, and the other reads them with unsigned integers when possible. I know this is not portable or cute, it is just an example that could get me started. With some help.
The code works, and I know it correctly, and I know how to write unit tests for it, but I don’t know how to prove it.
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
unsigned count_bytes1(unsigned char * bytes, unsigned len) {
unsigned count=0;
unsigned i;
for (i=0;i<len;i++) {
count+=bytes[i];
}
return count;
}
unsigned count_word(unsigned word) {
unsigned tmp = word;
if (sizeof(unsigned)==4) {
tmp = (0x00FF00FFU&tmp) + (( (0xFF00FF00U)&tmp)>>8);
tmp = (0x0000FFFFU&tmp) + (( (0xFFFF0000U)&tmp)>>16);
return tmp;
}
if (sizeof(unsigned)==8) {
tmp = (0x00FF00FF00FF00FFU&tmp) + (( (0xFF00FF00FF00FF00U)&tmp)>>8);
tmp = (0x0000FFFF0000FFFFU&tmp) + (( (0xFFFF0000FFFF0000U)&tmp)>>16);
tmp = (0x00000000FFFFFFFFU&tmp) + (( (0xFFFFFFFF00000000U)&tmp)>>32);
return tmp;
}
return tmp;
}
unsigned count_bytes2(unsigned char * bytes, unsigned len) {
unsigned count=0;
unsigned i;
for (i=0;i<len;) {
if ((unsigned long long)(bytes+i) % sizeof(unsigned) ==0) {
unsigned * words = (unsigned *) (bytes + i);
while (len-i >= sizeof(unsigned)) {
count += count_word (*words);
words++;
i+=sizeof(unsigned);
}
}
if (i<len) {
count+=bytes[i];
i++;
}
}
return count;
}
int main () {
unsigned char * bytes;
unsigned len=8192;
bytes=(unsigned char *)malloc(len);
len = read (0,bytes,len);
printf ("%u %u\n",count_bytes1(bytes,len),count_bytes2(bytes,len));
return 0;
}