view CONTRIBUTORS @ 827:a61728b58dc0

Fix array overflow bug in bdiff

I ran into a bug while importing a large repository into mercurial.
The diff algorithm does not allocate a big enough array of hunks
for some test cases. This results in memory corruption, and possibly,
as in my case, a seg fault.

You should be able to reproduce this problem with any case of more
than a few lines that follows this pattern:

a  b
=  =
1  1
   2
2  3
   4
3  5
   .
4  .
   .
5
.
.
.

I.e., "a" has blank lines on every other line that have been removed in
"b". In this case, the number of matching hunks is equal to the number
of lines in "b". This is more than ((an + bn)/4 + 2). I'm not sure what
motivates this formula, but when I changed it to the smaller of an or
bn (+ 1), it works.

[comment added by mpm]

Andrea Arcangeli <andrea at suse.de>
Thomas Arendsen Hein <thomas at intevation.de>
Goffredo Baroncelli <kreijack at libero.it>
Muli Ben-Yehuda <mulix at mulix.org>
Mikael Berthe <mikael at lilotux.net>
Vincent Danjean <vdanjean.ml at free.fr>
Jake Edge <jake at edge2.net>
Michael Fetterman <michael.fetterman at intel.com>
Edouard Gomez <ed.gomez at free.fr>
Alecs King <alecsk at gmail.com>
Vadim Lebedev <vadim at mbdsys.com>
Christopher Li <hg at chrisli.org>
Chris Mason <mason at suse.com>
Chad Netzer <chad.netzer at gmail.com>
Bryan O'Sullivan <bos at serpentine.com>
Vicent Seguí Pascual <vseguip at gmail.com>
Sean Perry <shaleh at speakeasy.net>
Nguyen Anh Quynh <aquynh at gmail.com>
Arun Sharma <arun at sharma-home.net>
Kevin Smith <yarcs at qualitycode.com>
Radoslaw Szkodzinski <astralstorm at gorzow.mm.pl>
K Thananchayan <thananck at yahoo.com>
Andrew Thompson <andrewkt at aktzero.com>
Michael S. Tsirkin <mst at mellanox.co.il>
Rafael Villar Burke <pachi at mmn-arquitectos.com>
Mark Williamson <mark.williamson at cl.cam.ac.uk>

If you are a contributor and don't see your name here, please let me know.