System.StackOverflowException

[karpiyon]

Hi,
Thanks for sharing your work.
I created a patch for a 170MB exe file. (I used IDA for that).
I am trying your C# code generate a diff to try to duplicate the patch.
While running the BsDiff I receive an overflow error in:
private static void Split(int[] I, int[] v, int start, int len, int h)

System.StackOverflowException
HResult=0x800703E9
Message=Exception of type 'System.StackOverflowException' was thrown.

Can it handle 170MB files?

Thanks

[bgrainger]

I think I have used this code to diff a file that large. Split is recursive, so it's plausible that on particular inputs it recurses to a great depth.

Are you using .NET Framework or .NET Core? Do you know what your maximum stack size is, and if it can be increased?

[karpiyon]

Hi,
Not sure which I use - I guess it targets .NETCore since I see this in the output log:
'BsDiffTool.exe' (CoreCLR: DefaultDomain): Loaded 'C:\Program Files\dotnet\shared\Microsoft.NETCore.App\7.0.3\System.Private.CoreLib.dll'.
'BsDiffTool.exe' (CoreCLR: clrhost): Loaded 'C:\Users\Chupi\source\repos\bsdiff.net\src\BsDiffTool\bin\Debug\net7.0\BsDiffTool.dll'.
And I have this?

As for the stack, I could try and increase it but to how much?
https://stackoverflow.com/questions/54584224/is-there-a-way-to-increase-the-stack-size-in-c

[karpiyon]

Can you think of anything which will solve this?

[bgrainger]

Are you able to share the files that cause the problem?

[NonsensicalLab]

I replaced the original Split method with the following code to avoid stack overflow problems

    private static void Split(int[] I, int[] v, int start, int len, int h)
    {
        Stack<int> starts = new Stack<int>();
        Stack<int> lens = new Stack<int>();
        Stack<TempValue?> temps = new Stack<TempValue?>();
        starts.Push(start);
        lens.Push(len);
        temps.Push(null);
        while (starts.Count > 0)
        {
            var crtStart = starts.Pop();
            var crtLen = lens.Pop();
            var crtTemp = temps.Pop();
            if (crtLen < 16)
            {
                int j;
                for (var k = crtStart; k < crtStart + crtLen; k += j)
                {
                    j = 1;
                    var x = v[I[k] + h];
                    for (var i = 1; k + i < crtStart + crtLen; i++)
                    {
                        if (v[I[k + i] + h] < x)
                        {
                            x = v[I[k + i] + h];
                            j = 0;
                        }
                        if (v[I[k + i] + h] == x)
                        {
                            Swap(ref I[k + j], ref I[k + i]);
                            j++;
                        }
                    }
                    for (var i = 0; i < j; i++)
                        v[I[k + i]] = k + j - 1;
                    if (j == 1)
                        I[k] = -1;
                }
            }
            else
            {
                if (crtTemp==null)
                {
                    var x = v[I[crtStart + crtLen / 2] + h];
                    var jj = 0;
                    var kk = 0;
                    for (var i2 = crtStart; i2 < crtStart + crtLen; i2++)
                    {
                        if (v[I[i2] + h] < x)
                            jj++;
                        if (v[I[i2] + h] == x)
                            kk++;
                    }
                    jj += crtStart;
                    kk += jj;

                    var i = crtStart;
                    var j = 0;
                    var k = 0;
                    while (i < jj)
                    {
                        if (v[I[i] + h] < x)
                        {
                            i++;
                        }
                        else if (v[I[i] + h] == x)
                        {
                            Swap(ref I[i], ref I[jj + j]);
                            j++;
                        }
                        else
                        {
                            Swap(ref I[i], ref I[kk + k]);
                            k++;
                        }
                    }

                    while (jj + j < kk)
                    {
                        if (v[I[jj + j] + h] == x)
                        {
                            j++;
                        }
                        else
                        {
                            Swap(ref I[jj + j], ref I[kk + k]);
                            k++;
                        }
                    }

                    if (jj > crtStart)
                    {
                        starts.Push(crtStart);
                        lens.Push(crtLen);
                        temps.Push(new TempValue(i,jj,kk)) ;


                        starts.Push(crtStart);
                        lens.Push(jj - crtStart);
                        temps.Push(null);
                        continue;
                    }
                    for (i = 0; i < kk - jj; i++)
                        v[I[jj + i]] = kk - 1;
                    if (jj == kk - 1)
                        I[jj] = -1;

                    if (crtStart + crtLen > kk)
                    {
                        starts.Push(kk);
                        lens.Push(crtStart + crtLen - kk);
                        temps.Push(null);
                    }
                }
                else
                {
                    for (crtTemp.i = 0; crtTemp.i < crtTemp.kk - crtTemp.jj; crtTemp.i++)
                        v[I[crtTemp.jj + crtTemp.i]] = crtTemp.kk - 1;
                    if (crtTemp.jj == crtTemp.kk - 1)
                        I[crtTemp.jj] = -1;
                    if (crtStart + crtLen > crtTemp.kk)
                    {
                        starts.Push(crtTemp.kk);
                        lens.Push(crtStart + crtLen - crtTemp.kk);
                        temps.Push(null);
                    }
                }
            }
        }

        static void Swap(ref int first, ref int second) => (second, first) = (first, second);
    }

    class TempValue
    {
        public int i;
        public int jj;
        public int kk;

        public TempValue(int i,  int jj, int kk)
        {
            this.i = i;
            this.jj = jj;
            this.kk = kk;
        }
    }