<?php
function strsamelen($str1, $str2, $s1idx=0, $s2idx=0) {
$len = min(strlen($str1)-$s1idx, strlen($str2)-$s2idx);
for($i = 0; $i < $len; $i++)
if ($str1{$i+$s1idx} != $str2{$i+$s2idx})
return $i;
return $i;
}
function strrsamelen($str1, $str2, $s1idx=null, $s2idx=null) {
if ($s1idx === null)
$s1idx = strlen($str1) - 1;
if ($s2idx === null)
$s2idx = strlen($str2) - 1;
$len = min($s1idx, $s2idx) + 1;
for($i = 0; $i < $len; $i++)
if ($str1{$s1idx-$i} != $str2{$s2idx-$i})
return $i;
return $i;
}
/*
* Text diff format:
* c [length]: common text of [length] characters
* o [length]: Text from old of [length] characters;
* after newline, [length] characters follow, followed
* by another newline
* n [length]: Text from new of [length] characters
*/
function difftotext($diffarray) {
$diffstring = "";
foreach ($diffarray as $diffelement) {
if ($diffelement[1] === null) {
$len = strlen($diffelement[0]);
$diffstring .= "c $len\n";
continue;
}
if (strlen($diffelement[0]) > 0) {
$len = strlen($diffelement[0]);
$diffstring .= "o $len\n{$diffelement[0]}\n";
}
if (strlen($diffelement[1]) > 0) {
$len = strlen($diffelement[1]);
$diffstring .= "n $len\n";
$diffstring .= "{$diffelement[1]}\n";
}
}
return $diffstring;
}
function texttodiff($diffstring, $pagetext, $forwards=false) {
$diffarray = array();
while(trim($diffstring)) {
$lines = explode("\n", $diffstring, 2);
$line = $lines[0];
$diffstring = $lines[1];
$type = $line{0};
$len = (int)substr($line, 1);
if ($type == 'c') {
array_push($diffarray, array(substr($pagetext, 0, $len), null));
$pagetext = substr($pagetext, $len);
} elseif ($type == 'o') {
$text = substr($diffstring, 0, $len);
$diffstring = substr($diffstring, $len + 1);
if ($forwards)
$pagetext = substr($pagetext, $len);
if (count($diffarray) > 0 && $diffarray[count($diffarray) - 1][1] !== null)
$diffarray[count($diffarray) - 1][0] .= $text;
else
array_push($diffarray, array($text, ""));
} elseif ($type == 'n') {
$text = substr($diffstring, 0, $len);
$diffstring = substr($diffstring, $len + 1);
if (!$forwards)
$pagetext = substr($pagetext, $len);
if (count($diffarray) > 0 && $diffarray[count($diffarray) - 1][1] !== null)
$diffarray[count($diffarray) - 1][1] .= $text;
else
array_push($diffarray, array("", $text));
}
}
return $diffarray;
}
function getnewrev($diffarray) {
$text = "";
while(count($diffarray)) {
$diffelement = array_shift($diffarray);
if ($diffelement[1] === null)
$text .= $diffelement[0];
else
$text .= $diffelement[1];
}
return $text;
}
function getoldrev($diffarray) {
$text = "";
while(count($diffarray)) {
$diffelement = array_shift($diffarray);
$text .= $diffelement[0];
}
return $text;
}
function istidyable($commonstring, $oldstring, $newstring) {
define("MAXTIDYLENGTH", 16);
define("TIDYFACTOR", 10);
if (strlen($commonstring) <= MAXTIDYLENGTH && (
strlen($oldstring) > strlen($commonstring) * TIDYFACTOR ||
strlen($newstring) > strlen($commonstring) * TIDYFACTOR))
return true;
return false;
}
function tidydiff($diffarray) {
$changed = false;
$tidyarray = array();
while(count($diffarray)) {
$diffelement = array_shift($diffarray);
if (count($tidyarray) == 0) {
array_push($tidyarray,$diffelement);
$tidyidx = 0;
continue;
}
if ($diffelement[1] === null) {
if ($tidyarray[$tidyidx][1] === null) {
$tidyarray[$tidyidx][0] .= $diffelement[0];
$changed = true;
} elseif (istidyable($diffelement[0],
$tidyarray[$tidyidx][0], $tidyarray[$tidyidx][1])) {
$tidyarray[$tidyidx][0] .= $diffelement[0];
$tidyarray[$tidyidx][1] .= $diffelement[0];
$changed = true;
} else {
array_push($tidyarray,$diffelement);
$tidyidx++;
}
} else {
if ($tidyarray[$tidyidx][1] !== null) {
$tidyarray[$tidyidx][0] .= $diffelement[0];
$tidyarray[$tidyidx][1] .= $diffelement[1];
$changed = true;
} elseif (istidyable($tidyarray[$tidyidx][0],
$diffelement[0], $diffelement[1])) {
$tidyarray[$tidyidx][1] = $tidyarray[$tidyidx][0];
$tidyarray[$tidyidx][0] .= $diffelement[0];
$tidyarray[$tidyidx][1] .= $diffelement[1];
$changed = true;
} else {
array_push($tidyarray,$diffelement);
$tidyidx++;
}
}
}
if ($changed)
$tidyarray = tidydiff($tidyarray);
return $tidyarray;
}
function stringdiff($oldtext, $newtext) {
define("MINLENGTH",3);
if (isset($_REQUEST["test"])) {
if ($oldtext == $newtext)
return array(array($oldtext,NULL));
$oldlines = explode("\n", $oldtext);
$newlines = explode("\n", $newtext);
$olddifflines = array(array(0,count($oldlines)-1));
$newdifflines = array(array(0,count($newlines)-1));
do {
$difflinesidx = 0;
$oldlinestart = -1;
$newlinestart = -1;
$matchdifflinesidx = -1;
$linecount = 0;
for ($oldline = 0; $oldline < count($oldlines) - 1; $oldline++) {
while ($oldline > $olddifflines[$difflinesidx][1])
$difflinesidx++;
if ($oldline < $olddifflines[$difflinesidx][0])
continue;
for ($newline = $newdifflines[$difflinesidx][0];
$newline <= $newdifflines[$difflinesidx][1]; $newline++) {
if ($oldlines[$oldline] == $newlines[$newline]) {
if ($oldline - $oldlinestart == $newline - $newlinestart &&
$oldlinestart + $linecount > $oldline)
continue;
$matchct = 0;
while (($oldlines[$oldline + $matchct] ==
$newlines[$newline + $matchct]) &&
$oldline + $matchct <= $olddifflines[$difflinesidx][1] &&
$newline + $matchct <= $newdifflines[$difflinesidx][1] &&
$oldline + $matchct < count($oldlines) - 1 &&
$newline + $matchct < count($newlines) - 1)
$matchct++;
if ($matchct > $linecount) {
$oldlinestart = $oldline;
$newlinestart = $newline;
$matchdifflinesidx = $difflinesidx;
$linecount = $matchct;
}
}
}
}
if ($linecount > 0) {
array_splice($olddifflines, $matchdifflinesidx, 1, array(
array(
$olddifflines[$matchdifflinesidx][0],
$oldlinestart - 1
), array(
$oldlinestart + $linecount,
$olddifflines[$matchdifflinesidx][1]
)));
array_splice($newdifflines, $matchdifflinesidx, 1, array(
array(
$newdifflines[$matchdifflinesidx][0],
$newlinestart - 1
), array(
$newlinestart + $linecount,
$newdifflines[$matchdifflinesidx][1]
)));
}
} while ($linecount > 0);
$diffarray = array();
for ($idx = 0; $idx < count($olddifflines) - 1; $idx++) {
$diffelement = array("","");
if ($olddifflines[$idx][0] <= $olddifflines[$idx][1])
$diffelement[0] = implode("\n",
array_slice($oldlines,$olddifflines[$idx][0],
$olddifflines[$idx][1]-$olddifflines[$idx][0]+1)) . "\n";
if ($newdifflines[$idx][0] <= $newdifflines[$idx][1])
$diffelement[1] = implode("\n",
array_slice($newlines,$newdifflines[$idx][0],
$newdifflines[$idx][1]-$newdifflines[$idx][0]+1)) . "\n";
if ($diffelement != array("",""))
array_push($diffarray,$diffelement);
$diffelement = array("",null);
$diffelement[0] = implode("\n",
array_slice($oldlines,$olddifflines[$idx][1]+1,
$olddifflines[$idx+1][0]-$olddifflines[$idx][1]-1));
if ($olddifflines[$idx+1][0] < count($oldlines))
$diffelement[0] .= "\n";
array_push($diffarray,$diffelement);
}
$diffelement = array("","");
if ($olddifflines[$idx][0] <= $olddifflines[$idx][1])
$diffelement[0] = implode("\n",
array_slice($oldlines,$olddifflines[$idx][0],
$olddifflines[$idx][1]-$olddifflines[$idx][0]+1));
if ($newdifflines[$idx][0] <= $newdifflines[$idx][1])
$diffelement[1] = implode("\n",
array_slice($newlines,$newdifflines[$idx][0],
$newdifflines[$idx][1]-$newdifflines[$idx][0]+1));
if ($diffelement != array("",""))
array_push($diffarray,$diffelement);
//echo("<!-- olddifflines:\n");
//var_dump($olddifflines);
//echo("\n--- oldlines:\n");
//var_dump($oldlines);
//echo("\n------ newdifflines:\n");
//var_dump($newdifflines);
//echo("\n--------- newlines:\n");
//var_dump($newlines);
//echo("\n------------ diffarray:\n");
//var_dump($diffarray);
//echo("\n-->\n");
} else {
if ($oldtext == $newtext) {
$beginlen = 0;
$endlen = 0;
} else {
$beginlen = strsamelen($oldtext, $newtext);
$begintext = substr($oldtext,0,$beginlen);
$oldtext = substr($oldtext,$beginlen);
$newtext = substr($newtext,$beginlen);
$endlen = strrsamelen($oldtext, $newtext);
$endtext = substr($oldtext,strlen($oldtext)-$endlen);
$oldtext = substr($oldtext,0,strlen($oldtext)-$endlen);
$newtext = substr($newtext,0,strlen($newtext)-$endlen);
}
$diffarray = array(array($oldtext,$newtext));
if ($beginlen > 0)
array_unshift($diffarray, array($begintext,null));
if ($endlen > 0)
array_push($diffarray, array($endtext,null));
}
do {
$rerun = false;
for ($i = 0; $i < count($diffarray); $i++) {
if ($diffarray[$i][1] === null)
continue;
$oldlen = strlen($diffarray[$i][0]);
$newlen = strlen($diffarray[$i][1]);
if ($oldlen <= MINLENGTH || $newlen <= MINLENGTH)
continue;
if ($oldlen <= $newlen) {
$short =& $diffarray[$i][0];
$shortlen = $oldlen;
$long =& $diffarray[$i][1];
$longlen = $newlen;
} else {
$short =& $diffarray[$i][1];
$shortlen = $newlen;
$long =& $diffarray[$i][0];
$longlen = $oldlen;
}
if (strpos($long, $short) !== false) {
$begintext = substr($long, 0, strpos($long, $short));
$endtext = substr($long, strpos($long, $short) + $shortlen);
$subarray = array(array($short,null));
if (strlen($begintext) > 0) {
if ($oldlen <= $newlen)
array_unshift($subarray,array("",$begintext));
else
array_unshift($subarray,array($begintext,""));
}
if (strlen($endtext) > 0) {
if ($oldlen <= $newlen)
array_push($subarray,array("",$endtext));
else
array_push($subarray,array($endtext,""));
}
array_splice($diffarray,$i,1,$subarray);
continue;
}
$matchlen = 0;
$divsize = 2;
while ($matchlen < $shortlen / $divsize && $shortlen / $divsize >= MINLENGTH) {
for ($dividx = 1; $dividx < $divsize; $dividx += 2) {
$shortmatchpos = (int)($shortlen / $divsize * $dividx);
$matchchar = $short{$shortmatchpos};
$longmatchpos = strpos($long, $matchchar);
while ($longmatchpos !== false) {
$curmatchflen = strsamelen($short, $long, $shortmatchpos, $longmatchpos);
$curmatchrlen = strrsamelen($short, $long, $shortmatchpos, $longmatchpos);
$curmatchlen = $curmatchflen + $curmatchrlen - 1;
if ($curmatchlen >= MINLENGTH && $curmatchlen > $matchlen) {
$matchlen = $curmatchlen;
$shortmatchstart = $shortmatchpos - $curmatchrlen + 1;
$longmatchstart = $longmatchpos - $curmatchrlen + 1;
}
$longmatchpos = strpos($long, $matchchar, $longmatchpos + 1);
}
}
$divsize *= 2;
}
if ($matchlen >= MINLENGTH) {
$subarray = array(array(substr($short,$shortmatchstart,$matchlen),null));
if ($shortmatchstart > 0 || $longmatchstart > 0) {
if ($oldlen <= $newlen)
array_unshift($subarray,array(
substr($short,0,$shortmatchstart),
substr($long,0,$longmatchstart)
));
else
array_unshift($subarray,array(
substr($long,0,$longmatchstart),
substr($short,0,$shortmatchstart)
));
}
if ($shortmatchstart + $matchlen < $shortlen || $longmatchstart + $matchlen < $longlen) {
if ($oldlen <= $newlen)
array_push($subarray,array(
substr($short,$shortmatchstart+$matchlen),
substr($long,$longmatchstart+$matchlen)
));
else
array_push($subarray,array(
substr($long,$longmatchstart+$matchlen),
substr($short,$shortmatchstart+$matchlen)
));
}
array_splice($diffarray,$i,1,$subarray);
$rerun = true;
}
}
} while ($rerun);
return tidydiff($diffarray);
}
?>
Notes: