捕捉数组越界访问问题

有时候，在数组上实现一个算法的时候，往往需要在算法中把数组分解成一些子数组。如果在这些子数组上出现越界访问，代表算法的实现有问题。但这些问题常常不容易发现。

这时候，可以用带有数组越界访问检测功能的重载数组来暂时替代这些子数组，来捕捉算法的实现的越界访问问题。

class array {
public:
        int *save;
        int save_len;

        int *a;
        int len;
        array(int *a, int len):a(a),len(len){
                save=a, save_len=len;
        }
        void moveto(int p) {
                if( &a[p]>save+save_len) {
                        printf("overflow at %d\n", &a[p]-save);
                }
                if (&a[p]<save) {
                        printf("underflow at %d\n", &a[p]-save);
                }
                a=&a[p];
        }
        void setlen(int l) {len=l;}
        int &operator[](int i) {
                int *p;

                if(i<0 || i>=len) printf("relative overflow at %d, relative a= &
s[%d], a.len=%d\n", 
                        i, a-save, len);
                p= &a[i];
                if(p<save) printf("underflow at %d, relative %d\n", p-save, p-a);
                if(p>save+save_len) printf("overflow at %d, relative %d\n", p-save, p-a);

                return *p;
        }
        void operator=(int *p) { moveto(p-a); }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

比如下面这个fib查找法的实现就有问题：

int search4(int key, int *a, int n)
{
        int *save=a;
        int fib, prev;
        int tmp;
        prev=0, fib=1;
        while(fib<n-1) {
                tmp = fib;
                fib+=prev;
                prev = tmp;
        }

        while(n>0) {
                while(n-1<fib){
                        tmp=prev;
                        prev = fib -prev;
                        fib=tmp;
                }

                tmp = fib-1;
                if (key <a[tmp]) n=fib;
                else if (key>a[tmp]) a=&a[tmp+1];
                else return &a[tmp]-save;
        }
        return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

替代之后变为：

int search4(int key, int *ar, int n)
{
        int *save=ar;
        int fib, prev;
        int tmp;
        array a(ar,n);

        prev=0, fib=1;
        while(fib<n-1) {
                tmp = fib;
                fib+=prev;
                prev = tmp;
        }

        while(n>0) {
                while(n-1<fib){
                        tmp=prev;
                        prev = fib -prev;
                        fib=tmp;
                }

                tmp = fib-1;
                if (key <a[tmp]) {n=fib;a.setlen(n);}
                else if (key>a[tmp]) {a=&a[tmp+1];a.setlen(a.len-tmp-1);}
                else return &a[tmp]-save;
        }
        return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

加上测试所需的main()函数：

int main()
{
        int a[21];

        int i;
        int n;
        n=sizeof(a)/sizeof(int);
        for(i=0; i<n;i++) a[i]=i;

        int u;
        for(u=0; u<10; u++) {
        i = search4(u, a, n);
        printf("i=%d\n", i);
        }
        return 0;        
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

编译之后，就可以把隐藏的越界访问查出来了。

i=0
i=1
i=2
relative overflow at 2, relative a= &s[3], a.len=2
i=3
i=4
relative overflow at 4, relative a= &s[5], a.len=3
i=5
relative overflow at 4, relative a= &s[5], a.len=3
i=6
i=7
relative overflow at 7, relative a= &s[8], a.len=5
i=8
relative overflow at 7, relative a= &s[8], a.len=5
i=9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15