Well here is a little description of what DrakX needs to work in comparison to the RH newt install. ******************************************************************************** * CVS ************************************************************************** ******************************************************************************** Like all good free software, DrakX is in CVS :) You can access it at http://www.mandrakelinux.com/cgi-bin/cvsweb.cgi/gi or via export CVS_RSH=ssh export CVSROOT=:ext:anoncvs@cvs.mandrakesoft.com:/cooker cvs checkout gi (enter password 'cvs') This is only read-only access. If you want more, tell me (pixel@mandrakesoft.com) Alas, all is not in CVS, a lot of things come from rpm packages which you must install. Please note that redoing *all* the stuff is not for the faint of heart. I myself sometimes wonder what the whole make does :-% Instead, changing some .pm files is quite easy (nice interpreted language) ******************************************************************************** * Making your custom install *************************************************** ******************************************************************************** If you have your own rpms you want to add, or make your own updated cdrom, you just have to issue: % gendistrib --noclean --distrib Where is the root of all the media that the install will see, this first one is the main one : (1) network or 1-cdrom installs DIRS == the root directory of the Distribution (2) multi-cdrom install DIRS == the root directories of all the media that the install will see ``gendistrib'' will scan the file Mandrake/base/hdlists in the main root directory (the first one in DIRS) to search for all media used. Typically you use Mandrake/RPMS* for RPM packages repository. For multi-cd, please use Mandrake/RPMS or Mandrake/RPMS1, Mandrake/RPMS2, etc. For one CD or a network/hd volume, please use Mandrake/RPMS. Optionnally, you can modify ``Mandrake/base/rpmsrate''; this file manages the relative importance of the files, and thus their installation or not. Also, mdkinst_stage2.gz must be remade if you modify files in Mandrake/mdkinst. See below for information about these files. ******************************************************************************** * FILES ************************************************************************ ******************************************************************************** First here are the different things needed : Mandrake/base/hdlists description of the available install media. format is one line for one medium as should be match regexp /hdlist\S*.cz2?/ for example (two cd install) you get hdlist1.cz Mandrake/RPMS1 Boot CD hdlist2.cz Mandrake/RPMS2 Extension CD Mandrake/base/hdlist*.cz table of rpm's headers, referred by ``hdlists'' their contents can be listed using ``packdrake -l '' or or ``parsehdlist ''. ! Need to be remade when Mandrake/RPMS* changes (with ``gendistrib'') ! Mandrake/base/depslist.ordered for each packages, tell which package it depends on. Also contains the size for some (obscure) bloody reasons. ! Need to be remade when Mandrake/RPMS* changes ! (with ``gendistrib --noclean --distrib .'') Mandrake/base/compssUsers Mandrake/base/rpmsrate ranks and classify packages, so that the installer will know which ones to install. format is : where is a symbolic name used in Mandrake/base/compssUsers* files, and defines importance level as described below : 5 must have 4 important 3 very nice 2 nice 1 maybe by default (for non expert), group selects packages for level 4 (important) and 5 (must have). export mode add 3 (very nice) level. other level (below 2) can only be selected using individual package selection. Mandrake/mdkinst live system used on certain installs. See ``Ramdisk or not'' below for more. Mandrake/base/mdkinst_stage2.bz2 for the ramdisk. live sytem in ext2 filesystem bzipped2. generated from Mandrake/mdkinst tree using misc/make_mdkinst_stage2 See ``Ramdisk or not'' below for more. Mandrake/base/rescue_stage2.bz2 rescue ramdisk. live sytem in ext2 filesystem bzipped2. this is the ramdisk loaded when typing rescue on boot prompt. there is no live system available, only the ramdisk is used. images/*.img floppy boot images to use with DrakX. Use: - cdrom.img for cdrom install - network.img + network_drivers.img for ftp/nfs install (non-pcmcia devices) - hd_grub.img for hard-disk install (see http://qa.mandrakesoft.com/hd_grub.cgi) - pcmcia.img for pcmcia install (see ``PCMCIA install'' below for more) images/boot.iso iso image to burn enabling any install (cdrom/hd/nfs/ftp) ******************************************************************************** * logs ************************************************************************* ******************************************************************************** During install, a lot of interesting stuff can be found in different places: in consoles and in files. To switch to console 2 for example, do Ctrl-Alt-F2 from the X install. - alt-F1: the stdout of the install. Not very interesting stuff - alt-F2: simple shell. Quite a lot of commands are available but as they are written in perl (for space), they do not handle the very same options as normal. After install, you can do ``chroot /mnt'' to see your system just like after rebooting. ``rpm -qa'' works for example. - alt-F3: a lot of interesting things. Be carefull, some ``ERROR'' messages are not interesting. - alt-F4: kernel's place. aka the output of dmesg. - alt-F7: the graphical install lives there - command "bug" puts on floppy lots of interesting stuff. - /tmp/stage1.log: same as alt-F3 part when stage1 run (e.g. actions before graphical install really begins) - /tmp/ddebug.log: (nearly the) same as latter alt-F3 part - /tmp/syslog: same as alt-F4 - /mnt/root/drakx/ddebug.log: at the end of each step, DrakX tries to backup /tmp/ddebug.log to /mnt/root/drakx. Available only after mounting of /. - /mnt/root/drakx/install.log: the log of the installation (or upgrade) of the rpms (just like rpm's /mnt/tmp/(install|upgrade).log) - /mnt/root/drakx/auto_inst.cfg.pl: a kickstart file generated at the end of each step. Can be used in 2 ways: kickstart install or ``defcfg'' install. Hopefully you know about kickstart. ``defcfg'' is a way to customize the default values in install. For example, French can be the default language with a qwerty keyboard, the auto-partitionning partitions can be changed, the default user class can be set to developer (!)... ******************************************************************************** * po translation files ********************************************************* ******************************************************************************** DrakX uses .po files for its translation. A script takes the different strings out of the .pm files. It generates the DrakX.pot file which contains all the english strings to translate. To add a new language, you just have to add it to lang.pm (if it's not there already) and put the .po in the perl-install/po directory (see ``Ramdisk or not'' to know if you have to regenerate the mdkinst_stage2.gz) ******************************************************************************** * PCMCIA install *************************************************************** ******************************************************************************** If the media you use to install is a pcmcia device, use the pcmcia boot disk. ******************************************************************************** * Ramdisk or not *************************************************************** ******************************************************************************** The DrakX install is much bigger than the newt one. So the ramdisk which was used is getting big, and costs a lot in memory (eg: the mdkinst_stage2 is 14MB - 23/09/99) (update! now size is 21MB - 24/01/01) (update! now size is 19MB - 26/04/01) | | newt | DrakX |-------+---------+---------------------------------------------------------- | nfs | live | live | ftp | ramdisk | ramdisk | http | ramdisk | ramdisk | hd | ramdisk | live if Mandrake/mdkinst/usr/bin/runinstall2 is a link, | | | ramdisk otherwise | cdrom | ramdisk | live if memory < 52MB, ramdisk otherwise Where ramdisk is needed, if detected memory is below the limit allowed for ramdisk (maintained in file gi/mdk-stage1/config-stage1.h; currently 52 Mb), a failure dialog will be printed explaining that there is not enough memory to perform the installation. When i say live, it means that the stage1 will *mount* the Mandrake/mdkinst and use it that way. The ramdisk is used in place of the live in some cases. This ramdisk is filled with mdkinst_stage2.gz For cdrom install, the ramdisk is used to speed up things (access time is quite high on cdrom drives) For pcmcia, it depends on the type of install. ******************************************************************************** * modules ********************************************************************** ******************************************************************************** Modules can be found in at least 2 places: - in /modules/modules.mar - in /lib/modules.cz /modules/modules.mar is used in mdk-stage1. It contains only modules interesting for one kind of install. For example in an hd install, it contains scsi modules. For a network install, it contains network card modules. (To create, extract or view files in a ``mar'' archive, please use gi/mdk-stage1/mar/mar; this is basically an archive format meant to be minimalistic) /lib/modules.cz contains all modules, it is used in stage2. To manually install a module during install, switch to console #2 and type "modprobe ". The modprobe program is a perl wrapper around /usr/bin/insmod. It uses the dependencies found in /modules/modules.dep (stage1). /usr/bin/insmod is a wrapper around /usr/bin/insmod_. It just extracts the module out of /lib/modules.cz in /tmp. Then it calls insmod_. /usr/bin/insmod_ is the real prog (which you usually find in /sbin/). You need to give it the complete path. ******************************************************************************** * Making screenshots *********************************************************** ******************************************************************************** 1. easy solution: press "F2"! 2. On a test machine, make a network install, switch to console (ctrl-alt-F2), enter: % xhost+ then, on another computer: % DISPLAY=test_machine:0 xwd -root | convert - screenshot.png ******************************************************************************** * Auto install ***************************************************************** ******************************************************************************** A powerful auto-install system is available. It allows performing an install without any human interaction. To feed automatic parameters to the stage1 part (the textmode part - might not be necessary for you if you plan to do cdrom-based auto-installs, but mostly highly needed when doing network installs), please refer to ../mdk-stage1/doc/TECH-INFOS. About the stage2 part (the actual installer, at the time you're (usually) running in graphical mode), please refer to the nice documentation written by David Eastcott. Either install the package "drakx-autoinstall-doc" from contrib, or browse: http://members.shaw.ca/mandrake/drakx/9.0/HTML/ The previous document will explain you how to setup the contents of the auto_inst.cfg file. Note that you have 3 alternatives for providing this file: - from a floppy disk; use "kickstart=floppy" as kernel parameter, as explained in the document - from the installation volume itself; put the file in the "Mandrake/base" directory of the installation volume; use "kickstart" only, or "kickstart=filename" to specify another filename than auto_inst.cfg - specified by the network; setup your DHCP server to provide the "bootfile" parameter, this file will be used as the "auto_inst.cfg" file; in this case you also need to provide the "netauto" boot parameter In any case, if the specified file ends with -IP or -IP.pl, IP will be substituted by the IP address of the machine, when doing a network install. Might be useful so that you can control all your auto installs from your server. ******************************************************************************** * Miscellaneous **************************************************************** ******************************************************************************** > o Media access methods: nfs, ftp, http, hd, cdrom > o Stages: init, stage1, stage2 > - What exactly each stage does init loads stage1 stage1 loads stage2, from various medium type stage2 is too big to fit on a floppy, that's why stage1 exists > - How each stage relates to the various media access methods stage1 knows only how to access to the media is compiled for. It contains only the kernel modules needed for that media. For eg, the nfs/ftp/http stage1 (network.img floppy) doesn't contain scsi modules nor ide. > - How one stage terminates and another begins. i.e., How does > stage1 find, mount, and launch stage2? /sbin/init just starts /sbin/stage1, and monitors its execution; it's here to cleanly umount the partitions when stage1 or stage2 dies/finished /sbin/stage1 takes care of mounting stage2 (in ramdisk if necessary) then it execs /usr/bin/runinstall2 (thus, stage2 replaces stage1, and init then monitors stage2) > o Text and Graphic mode installers > - Architectural overview of each have a look at gi/docs/object_class.fig ******************************************************************************** * OEM ************************************************************************** ******************************************************************************** > I am a system OEM in Bangalore,India selling systems bundled with > Mandrake Linux. The problem is that with every system I sell, I need to > install & configure the system which takes HOURS!. Can I do a diskcopy > instead? > > Please Help. This is a major bottleneck for me. many solutions: - make an install on drive hdb, then : dd if=/dev/hdb of=/dev/hdc but you should make sure the hardware is *REALLY* identical. - try the oem feature 3. - burn a cd out of *latest* cooker or 8.0 and above. - boot on it telling "oem" to syslinux !! it will destroy every data on the harddrive or resize (or use free space) if *ONLY* one fat partition is defined !! - you now have a very automated install matrix (duplicate it with "dd if=/dev/hdb of=/dev/hdc bs=1M count=730") put the harddrive in the oem box, the user will now have an *very* automated install, just asking the root password and user password, and some other question according its hardware. 4. just like 3. but you may have to mount /cdrom after typing rescue on syslinux prompt (oem script do it automatically if a automatic boot nfs network has been done as server is known). under /cdrom may be anything as long as it provides an installation tree of Mandrake Linux. after that run oem script by typing "/etc/oem -f" for normal installation or "/etc/oem -f server" for server installation (normal with server installed). 5. (just like 3. without burning a cd, doing the first part by hand) have a look at the /etc/oem script on the rescue and do it by hand... cu Pixel, fpons. comments: 1. maybe copy unnecessary things -> take too long solution -> use bs=8k count=xxxx 2. kernel_reread can be found on the new rescue, source is also at end of this mail. This solution works with one partition. Can be easily enhanced to many primary partitions... For extended partitions, more complicated, but not much :) 3. has just been added in latest cooker. It may still have some pb. The main current limitation is IDE only, though it can be fixed easily for special cases. -------------------------------------------------------------------------------- #include #include #include void die(char *msg) { perror(msg); exit(1); } void kernel_read(char *dev) { int fd; if ((fd = open(dev, O_RDONLY)) == -1) die("can't open device"); ioctl(fd, BLKRRPART, 0); close(fd); } int main(int argc, char **argv) { if (argc != 2) { fprintf(stderr, "usage: kernel_read_part \n"); exit(1); } kernel_read(argv[1]); } 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555

<?php
/**
*
* This file is part of the phpBB Forum Software package.
*
* @copyright (c) phpBB Limited <https://www.phpbb.com>
* @license GNU General Public License, version 2 (GPL-2.0)
*
* For full copyright and license information, please see
* the docs/CREDITS.txt file.
*
*/

/**
* @ignore
*/
if (!defined('IN_PHPBB'))
{
	exit;
}

/**
* Code from pear.php.net, Text_Diff-1.1.0 package
* http://pear.php.net/package/Text_Diff/ (native engine)
*
* Modified by phpBB Limited to meet our coding standards
* and being able to integrate into phpBB
*
* Class used internally by Text_Diff to actually compute the diffs. This
* class is implemented using native PHP code.
*
* The algorithm used here is mostly lifted from the perl module
* Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
* http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
*
* More ideas are taken from: http://www.ics.uci.edu/~eppstein/161/960229.html
*
* Some ideas (and a bit of code) are taken from analyze.c, of GNU
* diffutils-2.7, which can be found at:
* ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
*
* Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from
* Geoffrey T. Dairiki <dairiki@dairiki.org>. The original PHP version of this
* code was written by him, and is used/adapted with his permission.
*
* Copyright 2004-2008 The Horde Project (http://www.horde.org/)
*
* @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
* @package diff
*
* @access private
*/
class diff_engine
{
	/**
	* If set to true we trim all lines before we compare them. This ensures that sole space/tab changes do not trigger diffs.
	*/
	var $skip_whitespace_changes = true;

	function diff(&$from_lines, &$to_lines, $preserve_cr = true)
	{
		// Remove empty lines...
		// If preserve_cr is true, we basically only change \r\n and bare \r to \n to get the same carriage returns for both files
		// If it is false, we try to only use \n once per line and ommit all empty lines to be able to get a proper data diff

		if (is_array($from_lines))
		{
			$from_lines = implode("\n", $from_lines);
		}

		if (is_array($to_lines))
		{
			$to_lines = implode("\n", $to_lines);
		}

		if ($preserve_cr)
		{
			$from_lines = explode("\n", str_replace("\r", "\n", str_replace("\r\n", "\n", $from_lines)));
			$to_lines = explode("\n", str_replace("\r", "\n", str_replace("\r\n", "\n", $to_lines)));
		}
		else
		{
			$from_lines = explode("\n", preg_replace('#[\n\r]+#', "\n", $from_lines));
			$to_lines = explode("\n", preg_replace('#[\n\r]+#', "\n", $to_lines));
		}

		$n_from = count($from_lines);
		$n_to = count($to_lines);

		$this->xchanged = $this->ychanged = $this->xv = $this->yv = $this->xind = $this->yind = array();
		unset($this->seq, $this->in_seq, $this->lcs);

		// Skip leading common lines.
		for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++)
		{
			if (trim($from_lines[$skip]) !== trim($to_lines[$skip]))
			{
				break;
			}
			$this->xchanged[$skip] = $this->ychanged[$skip] = false;
		}

		// Skip trailing common lines.
		$xi = $n_from;
		$yi = $n_to;

		for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++)
		{
			if (trim($from_lines[$xi]) !== trim($to_lines[$yi]))
			{
				break;
			}
			$this->xchanged[$xi] = $this->ychanged[$yi] = false;
		}

		// Ignore lines which do not exist in both files.
		for ($xi = $skip; $xi < $n_from - $endskip; $xi++)
		{
			if ($this->skip_whitespace_changes) $xhash[trim($from_lines[$xi])] = 1; else $xhash[$from_lines[$xi]] = 1;
		}

		for ($yi = $skip; $yi < $n_to - $endskip; $yi++)
		{
			$line = ($this->skip_whitespace_changes) ? trim($to_lines[$yi]) : $to_lines[$yi];

			if (($this->ychanged[$yi] = empty($xhash[$line])))
			{
				continue;
			}
			$yhash[$line] = 1;
			$this->yv[] = $line;
			$this->yind[] = $yi;
		}

		for ($xi = $skip; $xi < $n_from - $endskip; $xi++)
		{
			$line = ($this->skip_whitespace_changes) ? trim($from_lines[$xi]) : $from_lines[$xi];

			if (($this->xchanged[$xi] = empty($yhash[$line])))
			{
				continue;
			}
			$this->xv[] = $line;
			$this->xind[] = $xi;
		}

		// Find the LCS.
		$this->_compareseq(0, count($this->xv), 0, count($this->yv));

		// Merge edits when possible.
		if ($this->skip_whitespace_changes)
		{
			$from_lines_clean = array_map('trim', $from_lines);
			$to_lines_clean = array_map('trim', $to_lines);

			$this->_shift_boundaries($from_lines_clean, $this->xchanged, $this->ychanged);
			$this->_shift_boundaries($to_lines_clean, $this->ychanged, $this->xchanged);

			unset($from_lines_clean, $to_lines_clean);
		}
		else
		{
			$this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
			$this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
		}

		// Compute the edit operations.
		$edits = array();
		$xi = $yi = 0;

		while ($xi < $n_from || $yi < $n_to)
		{
			// Skip matching "snake".
			$copy = array();

			while ($xi < $n_from && $yi < $n_to && !$this->xchanged[$xi] && !$this->ychanged[$yi])
			{
				$copy[] = $from_lines[$xi++];
				$yi++;
			}

			if ($copy)
			{
				$edits[] = new diff_op_copy($copy);
			}

			// Find deletes & adds.
			$delete = array();
			while ($xi < $n_from && $this->xchanged[$xi])
			{
				$delete[] = $from_lines[$xi++];
			}

			$add = array();
			while ($yi < $n_to && $this->ychanged[$yi])
			{
				$add[] = $to_lines[$yi++];
			}

			if ($delete && $add)
			{
				$edits[] = new diff_op_change($delete, $add);
			}
			else if ($delete)
			{
				$edits[] = new diff_op_delete($delete);
			}
			else if ($add)
			{
				$edits[] = new diff_op_add($add);
			}
		}

		return $edits;
	}

	/**
	* Divides the Largest Common Subsequence (LCS) of the sequences (XOFF,
	* XLIM) and (YOFF, YLIM) into NCHUNKS approximately equally sized segments.
	*
	* Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an array of
	* NCHUNKS+1 (X, Y) indexes giving the diving points between sub
	* sequences.  The first sub-sequence is contained in (X0, X1), (Y0, Y1),
	* the second in (X1, X2), (Y1, Y2) and so on.  Note that (X0, Y0) ==
	* (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
	*
	* This function assumes that the first lines of the specified portions of
	* the two files do not match, and likewise that the last lines do not
	* match.  The caller must trim matching lines from the beginning and end
	* of the portions it is going to specify.
	*/
	function _diag($xoff, $xlim, $yoff, $ylim, $nchunks)
	{
		$flip = false;

		if ($xlim - $xoff > $ylim - $yoff)
		{
			// Things seems faster (I'm not sure I understand why) when the shortest sequence is in X.
			$flip = true;
			list($xoff, $xlim, $yoff, $ylim) = array($yoff, $ylim, $xoff, $xlim);
		}

		if ($flip)
		{
			for ($i = $ylim - 1; $i >= $yoff; $i--)
			{
				$ymatches[$this->xv[$i]][] = $i;
			}
		}
		else
		{
			for ($i = $ylim - 1; $i >= $yoff; $i--)
			{
				$ymatches[$this->yv[$i]][] = $i;
			}
		}

		$this->lcs = 0;
		$this->seq[0]= $yoff - 1;
		$this->in_seq = array();
		$ymids[0] = array();

		$numer = $xlim - $xoff + $nchunks - 1;
		$x = $xoff;

		for ($chunk = 0; $chunk < $nchunks; $chunk++)
		{
			if ($chunk > 0)
			{
				for ($i = 0; $i <= $this->lcs; $i++)
				{
					$ymids[$i][$chunk - 1] = $this->seq[$i];
				}
			}

			$x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $chunk) / $nchunks);

			for (; $x < $x1; $x++)
			{
				$line = $flip ? $this->yv[$x] : $this->xv[$x];
				if (empty($ymatches[$line]))
				{
					continue;
				}
				$matches = $ymatches[$line];

				reset($matches);
				while (list(, $y) = each($matches))
				{
					if (empty($this->in_seq[$y]))
					{
						$k = $this->_lcs_pos($y);
						$ymids[$k] = $ymids[$k - 1];
						break;
					}
				}

				// no reset() here
				while (list(, $y) = each($matches))
				{
					if ($y > $this->seq[$k - 1])
					{
						// Optimization: this is a common case: next match is just replacing previous match.
						$this->in_seq[$this->seq[$k]] = false;
						$this->seq[$k] = $y;
						$this->in_seq[$y] = 1;
					}
					else if (empty($this->in_seq[$y]))
					{
						$k = $this->_lcs_pos($y);
						$ymids[$k] = $ymids[$k - 1];
					}
				}
			}
		}

		$seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
		$ymid = $ymids[$this->lcs];

		for ($n = 0; $n < $nchunks - 1; $n++)
		{
			$x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
			$y1 = $ymid[$n] + 1;
			$seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
		}
		$seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);

		return array($this->lcs, $seps);
	}

	function _lcs_pos($ypos)
	{
		$end = $this->lcs;

		if ($end == 0 || $ypos > $this->seq[$end])
		{
			$this->seq[++$this->lcs] = $ypos;
			$this->in_seq[$ypos] = 1;
			return $this->lcs;
		}

		$beg = 1;
		while ($beg < $end)
		{
			$mid = (int)(($beg + $end) / 2);
			if ($ypos > $this->seq[$mid])
			{
				$beg = $mid + 1;
			}
			else
			{
				$end = $mid;
			}
		}

		$this->in_seq[$this->seq[$end]] = false;
		$this->seq[$end] = $ypos;
		$this->in_seq[$ypos] = 1;

		return $end;
	}

	/**
	* Finds LCS of two sequences.
	*
	* The results are recorded in the vectors $this->{x,y}changed[], by
	* storing a 1 in the element for each line that is an insertion or
	* deletion (ie. is not in the LCS).
	*
	* The subsequence of file 0 is (XOFF, XLIM) and likewise for file 1.
	*
	* Note that XLIM, YLIM are exclusive bounds.  All line numbers are
	* origin-0 and discarded lines are not counted.
	*/
	function _compareseq($xoff, $xlim, $yoff, $ylim)
	{
		// Slide down the bottom initial diagonal.
		while ($xoff < $xlim && $yoff < $ylim && $this->xv[$xoff] == $this->yv[$yoff])
		{
			++$xoff;
			++$yoff;
		}

		// Slide up the top initial diagonal.
		while ($xlim > $xoff && $ylim > $yoff && $this->xv[$xlim - 1] == $this->yv[$ylim - 1])
		{
			--$xlim;
			--$ylim;
		}

		if ($xoff == $xlim || $yoff == $ylim)
		{
			$lcs = 0;
		}
		else
		{
			// This is ad hoc but seems to work well.
			// $nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
			// $nchunks = max(2,min(8,(int)$nchunks));
			$nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
			list($lcs, $seps) = $this->_diag($xoff, $xlim, $yoff, $ylim, $nchunks);
		}

		if ($lcs == 0)
		{
			// X and Y sequences have no common subsequence: mark all changed.
			while ($yoff < $ylim)
			{
				$this->ychanged[$this->yind[$yoff++]] = 1;
			}

			while ($xoff < $xlim)
			{
				$this->xchanged[$this->xind[$xoff++]] = 1;
			}
		}
		else
		{
			// Use the partitions to split this problem into subproblems.
			reset($seps);
			$pt1 = $seps[0];

			while ($pt2 = next($seps))
			{
				$this->_compareseq($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
				$pt1 = $pt2;
			}
		}
	}

	/**
	* Adjusts inserts/deletes of identical lines to join changes as much as possible.
	*
	* We do something when a run of changed lines include a line at one end
	* and has an excluded, identical line at the other.  We are free to
	* choose which identical line is included. 'compareseq' usually chooses
	* the one at the beginning, but usually it is cleaner to consider the
	* following identical line to be the "change".
	*
	* This is extracted verbatim from analyze.c (GNU diffutils-2.7).
	*/
	function _shift_boundaries($lines, &$changed, $other_changed)
	{
		$i = 0;
		$j = 0;

		$len = count($lines);
		$other_len = count($other_changed);

		while (1)
		{
			// Scan forward to find the beginning of another run of
			// changes. Also keep track of the corresponding point in the other file.
			//