176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* ----------------------------------------------------------------------- *
276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *
376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   Copyright 2007-2008 H. Peter Anvin - All Rights Reserved
476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   Copyright 2009 Intel Corporation; author: H. Peter Anvin
576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *
676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   Permission is hereby granted, free of charge, to any person
776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   obtaining a copy of this software and associated documentation
876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   files (the "Software"), to deal in the Software without
976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   restriction, including without limitation the rights to use,
1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   copy, modify, merge, publish, distribute, sublicense, and/or
1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   sell copies of the Software, and to permit persons to whom
1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   the Software is furnished to do so, subject to the following
1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   conditions:
1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *
1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   The above copyright notice and this permission notice shall
1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   be included in all copies or substantial portions of the Software.
1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *
1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *   OTHER DEALINGS IN THE SOFTWARE.
2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *
2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * ----------------------------------------------------------------------- */
2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*
3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * movebits.c
3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *
3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Utility function to take a list of memory areas to shuffle and
3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * convert it to a set of shuffle operations.
3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *
3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Note: a lot of the functions in this file deal with "parent pointers",
3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * which are pointers to a pointer to a list, or part of the list.
3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * They can be pointers to a variable holding the list root pointer,
3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * or pointers to a next field of a previous entry.
3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */
4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <assert.h>
4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdio.h>
4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <errno.h>
4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdlib.h>
4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <inttypes.h>
4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <setjmp.h>
4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <minmax.h>
4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdbool.h>
4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <syslinux/movebits.h>
5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <dprintf.h>
5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic jmp_buf new_movelist_bail;
5476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
5576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic struct syslinux_movelist *new_movelist(addr_t dst, addr_t src,
5676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman					      addr_t len)
5776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
5876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *ml = malloc(sizeof(struct syslinux_movelist));
5976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
6076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (!ml)
6176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	longjmp(new_movelist_bail, 1);
6276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
6376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    ml->dst = dst;
6476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    ml->src = src;
6576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    ml->len = len;
6676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    ml->next = NULL;
6776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
6876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    return ml;
6976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
7076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
7176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic struct syslinux_movelist *dup_movelist(struct syslinux_movelist *src)
7276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
7376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *dst = NULL, **dstp = &dst, *ml;
7476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
7576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    while (src) {
7676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	ml = new_movelist(src->dst, src->src, src->len);
7776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	*dstp = ml;
7876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dstp = &ml->next;
7976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	src = src->next;
8076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
8176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
8276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    return dst;
8376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
8476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
8576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void
8676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanadd_freelist(struct syslinux_memmap **mmap, addr_t start,
8776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	     addr_t len, enum syslinux_memmap_types type)
8876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
8976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (syslinux_add_memmap(mmap, start, len, type))
9076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	longjmp(new_movelist_bail, 1);
9176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
9276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
9376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*
9476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Take a chunk, entirely confined in **parentptr, and split it off so that
9576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * it has its own structure.
9676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */
9776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic struct syslinux_movelist **split_movelist(addr_t start, addr_t len,
9876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman						 struct syslinux_movelist
9976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman						 **parentptr)
10076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
10176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *m, *ml = *parentptr;
10276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
10376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    assert(start >= ml->src);
10476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    assert(start < ml->src + ml->len);
10576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
10676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    /* Split off the beginning */
10776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (start > ml->src) {
10876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	addr_t l = start - ml->src;
10976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
11076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	m = new_movelist(ml->dst + l, start, ml->len - l);
11176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	m->next = ml->next;
11276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	ml->len = l;
11376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	ml->next = m;
11476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
11576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	parentptr = &ml->next;
11676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	ml = m;			/* Continue processing the new node */
11776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
11876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
11976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    /* Split off the end */
12076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (ml->len > len) {
12176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	addr_t l = ml->len - len;
12276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
12376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	m = new_movelist(ml->dst + len, ml->src + len, l);
12476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	m->next = ml->next;
12576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	ml->len = len;
12676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	ml->next = m;
12776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
12876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
12976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    return parentptr;
13076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
13176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
13276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void delete_movelist(struct syslinux_movelist **parentptr)
13376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
13476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *o = *parentptr;
13576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    *parentptr = o->next;
13676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    free(o);
13776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
13876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
13976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void free_movelist(struct syslinux_movelist **parentptr)
14076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
14176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    while (*parentptr)
14276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	delete_movelist(parentptr);
14376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
14476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
14576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*
14676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Scan the freelist looking for a particular chunk of memory.  Returns
14776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * the memmap chunk containing to the first byte of the region.
14876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */
14976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic const struct syslinux_memmap *is_free_zone(const struct syslinux_memmap
15076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman						  *list, addr_t start,
15176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman						  addr_t len)
15276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
15376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t last, llast;
15476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
15576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("f: 0x%08x bytes at 0x%08x\n", len, start);
15676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
15776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    last = start + len - 1;
15876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
15976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    while (list->type != SMT_END) {
16076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (list->start <= start) {
16176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    const struct syslinux_memmap *ilist = list;
16276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    while (valid_terminal_type(list->type)) {
16376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		llast = list->next->start - 1;
16476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		if (llast >= last)
16576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    return ilist;
16676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		list = list->next;
16776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
16876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
16976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (list->start > start)
17076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		return NULL;	/* Invalid type in region */
17176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
17276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	list = list->next;
17376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
17476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
17576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    return NULL;		/* Internal error? */
17676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
17776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
17876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*
17976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Scan the freelist looking for the smallest chunk of memory which
18076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * can fit X bytes; returns the length of the block on success.
18176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */
18276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic addr_t free_area(const struct syslinux_memmap *mmap,
18376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman			addr_t len, addr_t * start)
18476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
18576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    const struct syslinux_memmap *best = NULL;
18676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    const struct syslinux_memmap *s;
18776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t slen, best_len = -1;
18876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
18976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    for (s = mmap; s->type != SMT_END; s = s->next) {
19076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (s->type != SMT_FREE)
19176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    continue;
19276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	slen = s->next->start - s->start;
19376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (slen >= len) {
19476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (!best || best_len > slen) {
19576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		best = s;
19676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		best_len = slen;
19776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
19876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
19976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
20076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
20176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (best) {
20276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	*start = best->start;
20376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	return best_len;
20476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    } else {
20576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	return 0;
20676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
20776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
20876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
20976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*
21076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Remove a chunk from the freelist
21176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */
21276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void
21376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanallocate_from(struct syslinux_memmap **mmap, addr_t start, addr_t len)
21476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
21576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    syslinux_add_memmap(mmap, start, len, SMT_ALLOC);
21676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
21776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
21876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*
21976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * Find chunks of a movelist which are one-to-many (one source, multiple
22076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * destinations.)  Those chunks can get turned into post-shuffle copies,
22176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * to avoid confusing the shuffler.
22276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */
22376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void shuffle_dealias(struct syslinux_movelist **fraglist,
22476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman			    struct syslinux_movelist **postcopy)
22576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
22676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *mp, **mpp, *mx, *np;
22776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t ps, pe, xs, xe, delta;
22876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    bool advance;
22976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
23076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("Before alias resolution:\n");
23176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    syslinux_dump_movelist(*fraglist);
23276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
23376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    *postcopy = NULL;
23476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
23576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    /*
23676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman     * Note: as written, this is an O(n^2) algorithm; by producing a list
23776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman     * sorted by destination address we could reduce it to O(n log n).
23876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman     */
23976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    mpp = fraglist;
24076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    while ((mp = *mpp)) {
24176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("mp -> (%#x,%#x,%#x)\n", mp->dst, mp->src, mp->len);
24276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	ps = mp->src;
24376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	pe = mp->src + mp->len - 1;
24476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	for (mx = *fraglist; mx != mp; mx = mx->next) {
24576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    dprintf("mx -> (%#x,%#x,%#x)\n", mx->dst, mx->src, mx->len);
24676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    /*
24776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	     * If there is any overlap between mx and mp, mp should be
24876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	     * modified and possibly split.
24976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	     */
25076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    xs = mx->src;
25176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    xe = mx->src + mx->len - 1;
25276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
25376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    dprintf("?: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe);
25476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
25576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (pe <= xs || ps >= xe)
25676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		continue;	/* No overlap */
25776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
25876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    advance = false;
25976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    *mpp = mp->next;	/* Remove from list */
26076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
26176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (pe > xe) {
26276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		delta = pe - xe;
26376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		np = new_movelist(mp->dst + mp->len - delta,
26476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman				  mp->src + mp->len - delta, delta);
26576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		mp->len -= delta;
26676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		pe = xe;
26776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		np->next = *mpp;
26876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		*mpp = np;
26976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		advance = true;
27076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
27176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (ps < xs) {
27276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		delta = xs - ps;
27376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		np = new_movelist(mp->dst, ps, delta);
27476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		mp->src += delta;
27576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		ps = mp->src;
27676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		mp->dst += delta;
27776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		mp->len -= delta;
27876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		np->next = *mpp;
27976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		*mpp = np;
28076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		advance = true;
28176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
28276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
28376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    assert(ps >= xs && pe <= xe);
28476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
28576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    dprintf("Overlap: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe);
28676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
28776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    mp->src = mx->dst + (ps - xs);
28876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    mp->next = *postcopy;
28976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    *postcopy = mp;
29076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
29176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    mp = *mpp;
29276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
29376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (!advance)
29476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		goto restart;
29576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
29676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
29776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	mpp = &mp->next;
29876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanrestart:
29976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	;
30076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
30176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
30276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("After alias resolution:\n");
30376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    syslinux_dump_movelist(*fraglist);
30476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("Post-shuffle copies:\n");
30576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    syslinux_dump_movelist(*postcopy);
30676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
30776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
30876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*
30976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * The code to actually emit moving of a chunk into its final place.
31076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */
31176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void
31276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanmove_chunk(struct syslinux_movelist ***moves,
31376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	   struct syslinux_memmap **mmap,
31476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	   struct syslinux_movelist **fp, addr_t copylen)
31576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
31676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t copydst, copysrc;
31776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t freebase, freelen;
31876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t needlen;
31976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    int reverse;
32076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *f = *fp, *mv;
32176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
32276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (f->src < f->dst && (f->dst - f->src) < f->len) {
32376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	/* "Shift up" type overlap */
32476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	needlen = f->dst - f->src;
32576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	reverse = 1;
32676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    } else if (f->src > f->dst && (f->src - f->dst) < f->len) {
32776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	/* "Shift down" type overlap */
32876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	needlen = f->src - f->dst;
32976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	reverse = 0;
33076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    } else {
33176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	needlen = f->len;
33276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	reverse = 0;
33376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
33476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
33576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    copydst = f->dst;
33676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    copysrc = f->src;
33776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
33876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("Q: copylen = 0x%08x, needlen = 0x%08x\n", copylen, needlen);
33976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
34076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (copylen < needlen) {
34176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (reverse) {
34276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    copydst += (f->len - copylen);
34376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    copysrc += (f->len - copylen);
34476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
34576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
34676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("X: 0x%08x bytes at 0x%08x -> 0x%08x\n",
34776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copylen, copysrc, copydst);
34876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
34976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	/* Didn't get all we wanted, so we have to split the chunk */
35076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	fp = split_movelist(copysrc, copylen, fp);	/* Is this right? */
35176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	f = *fp;
35276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
35376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
35476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    mv = new_movelist(f->dst, f->src, f->len);
35576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n", mv->len, mv->src, mv->dst);
35676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    **moves = mv;
35776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    *moves = &mv->next;
35876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
35976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    /* Figure out what memory we just freed up */
36076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (f->dst > f->src) {
36176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	freebase = f->src;
36276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	freelen = min(f->len, f->dst - f->src);
36376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    } else if (f->src >= f->dst + f->len) {
36476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	freebase = f->src;
36576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	freelen = f->len;
36676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    } else {
36776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	freelen = f->src - f->dst;
36876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	freebase = f->dst + f->len;
36976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
37076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
37176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("F: 0x%08x bytes at 0x%08x\n", freelen, freebase);
37276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
37376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    add_freelist(mmap, freebase, freelen, SMT_FREE);
37476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
37576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    delete_movelist(fp);
37676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
37776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
37876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*
37976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * moves is computed from "frags" and "freemem".  "space" lists
38076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman * free memory areas at our disposal, and is (src, cnt) only.
38176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */
38276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanint
38376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmansyslinux_compute_movelist(struct syslinux_movelist **moves,
38476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman			  struct syslinux_movelist *ifrags,
38576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman			  struct syslinux_memmap *memmap)
38676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
38776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_memmap *mmap = NULL;
38876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    const struct syslinux_memmap *mm, *ep;
38976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *frags = NULL;
39076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *postcopy = NULL;
39176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *mv;
39276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *f, **fp;
39376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *o, **op;
39476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t needbase, needlen, copysrc, copydst, copylen;
39576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t avail;
39676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t fstart, flen;
39776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t cbyte;
39876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    addr_t ep_len;
39976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    int rv = -1;
40076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    int reverse;
40176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
40276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("entering syslinux_compute_movelist()...\n");
40376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
40476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (setjmp(new_movelist_bail)) {
40576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmannomem:
40676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("Out of working memory!\n");
40776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	goto bail;
40876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
40976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
41076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    *moves = NULL;
41176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
41276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    /* Create our memory map.  Anything that is SMT_FREE or SMT_ZERO is
41376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman       fair game, but mark anything used by source material as SMT_ALLOC. */
41476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    mmap = syslinux_init_memmap();
41576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (!mmap)
41676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	goto nomem;
41776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
41876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    frags = dup_movelist(ifrags);
41976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
42076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    /* Process one-to-many conditions */
42176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    shuffle_dealias(&frags, &postcopy);
42276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
42376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    for (mm = memmap; mm->type != SMT_END; mm = mm->next)
42476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	add_freelist(&mmap, mm->start, mm->next->start - mm->start,
42576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		     mm->type == SMT_ZERO ? SMT_FREE : mm->type);
42676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
42776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    for (f = frags; f; f = f->next)
42876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	add_freelist(&mmap, f->src, f->len, SMT_ALLOC);
42976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
43076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    /* As long as there are unprocessed fragments in the chain... */
43176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    while ((fp = &frags, f = *fp)) {
43276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
43376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("Current free list:\n");
43476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	syslinux_dump_memmap(mmap);
43576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("Current frag list:\n");
43676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	syslinux_dump_movelist(frags);
43776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
43876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	/* Scan for fragments which can be discarded without action. */
43976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (f->src == f->dst) {
44076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    delete_movelist(fp);
44176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    continue;
44276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
44376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	op = &f->next;
44476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	while ((o = *op)) {
44576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (o->src == o->dst)
44676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		delete_movelist(op);
44776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    else
44876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		op = &o->next;
44976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
45076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
45176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	/* Scan for fragments which can be immediately moved
45276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	   to their final destination, if so handle them now */
45376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	for (op = fp; (o = *op); op = &o->next) {
45476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (o->src < o->dst && (o->dst - o->src) < o->len) {
45576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		/* "Shift up" type overlap */
45676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		needlen = o->dst - o->src;
45776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		needbase = o->dst + (o->len - needlen);
45876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		reverse = 1;
45976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		cbyte = o->dst + o->len - 1;
46076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    } else if (o->src > o->dst && (o->src - o->dst) < o->len) {
46176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		/* "Shift down" type overlap */
46276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		needlen = o->src - o->dst;
46376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		needbase = o->dst;
46476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		reverse = 0;
46576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		cbyte = o->dst;	/* "Critical byte" */
46676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    } else {
46776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		needlen = o->len;
46876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		needbase = o->dst;
46976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		reverse = 0;
47076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		cbyte = o->dst;	/* "Critical byte" */
47176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
47276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
47376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (is_free_zone(mmap, needbase, needlen)) {
47476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		fp = op, f = o;
47576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		dprintf("!: 0x%08x bytes at 0x%08x -> 0x%08x\n",
47676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman			f->len, f->src, f->dst);
47776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copysrc = f->src;
47876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copylen = needlen;
47976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		allocate_from(&mmap, needbase, copylen);
48076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		goto move_chunk;
48176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
48276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
48376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
48476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	/* Ok, bother.  Need to do real work at least with one chunk. */
48576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
48676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n",
48776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		f->len, f->src, f->dst);
48876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
48976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	/* See if we can move this chunk into place by claiming
49076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	   the destination, or in the case of partial overlap, the
49176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	   missing portion. */
49276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
49376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (f->src < f->dst && (f->dst - f->src) < f->len) {
49476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    /* "Shift up" type overlap */
49576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    needlen = f->dst - f->src;
49676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    needbase = f->dst + (f->len - needlen);
49776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    reverse = 1;
49876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    cbyte = f->dst + f->len - 1;
49976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	} else if (f->src > f->dst && (f->src - f->dst) < f->len) {
50076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    /* "Shift down" type overlap */
50176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    needlen = f->src - f->dst;
50276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    needbase = f->dst;
50376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    reverse = 0;
50476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    cbyte = f->dst;	/* "Critical byte" */
50576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	} else {
50676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    needlen = f->len;
50776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    needbase = f->dst;
50876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    reverse = 0;
50976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    cbyte = f->dst;
51076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
51176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
51276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("need: base = 0x%08x, len = 0x%08x, "
51376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		"reverse = %d, cbyte = 0x%08x\n",
51476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		needbase, needlen, reverse, cbyte);
51576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
51676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	ep = is_free_zone(mmap, cbyte, 1);
51776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (ep) {
51876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    ep_len = ep->next->start - ep->start;
51976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (reverse)
52076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		avail = needbase + needlen - ep->start;
52176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    else
52276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		avail = ep_len - (needbase - ep->start);
52376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	} else {
52476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    avail = 0;
52576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
52676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
52776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (avail) {
52876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    /* We can move at least part of this chunk into place without
52976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	       further ado */
53076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    dprintf("space: start 0x%08x, len 0x%08x, free 0x%08x\n",
53176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    ep->start, ep_len, avail);
53276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    copylen = min(needlen, avail);
53376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
53476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (reverse)
53576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		allocate_from(&mmap, needbase + needlen - copylen, copylen);
53676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    else
53776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		allocate_from(&mmap, needbase, copylen);
53876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
53976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    goto move_chunk;
54076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
54176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
54276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	/* At this point, we need to evict something out of our space.
54376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	   Find the object occupying the critical byte of our target space,
54476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	   and move it out (the whole object if we can, otherwise a subset.)
54576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	   Then move a chunk of ourselves into place. */
54676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	for (op = &f->next, o = *op; o; op = &o->next, o = *op) {
54776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
54876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    dprintf("O: 0x%08x bytes at 0x%08x -> 0x%08x\n",
54976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    o->len, o->src, o->dst);
55076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
55176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (!(o->src <= cbyte && o->src + o->len > cbyte))
55276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		continue;	/* Not what we're looking for... */
55376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
55476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    /* Find somewhere to put it... */
55576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
55676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (is_free_zone(mmap, o->dst, o->len)) {
55776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		/* Score!  We can move it into place directly... */
55876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copydst = o->dst;
55976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copysrc = o->src;
56076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copylen = o->len;
56176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    } else if (free_area(mmap, o->len, &fstart)) {
56276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		/* We can move the whole chunk */
56376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copydst = fstart;
56476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copysrc = o->src;
56576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copylen = o->len;
56676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    } else {
56776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		/* Well, copy as much as we can... */
56876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		if (syslinux_memmap_largest(mmap, SMT_FREE, &fstart, &flen)) {
56976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    dprintf("No free memory at all!\n");
57076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    goto bail;	/* Stuck! */
57176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		}
57276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
57376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		/* Make sure we include the critical byte */
57476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		copydst = fstart;
57576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		if (reverse) {
57676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    copysrc = max(o->src, cbyte + 1 - flen);
57776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    copylen = cbyte + 1 - copysrc;
57876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		} else {
57976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    copysrc = cbyte;
58076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    copylen = min(flen, o->len - (cbyte - o->src));
58176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		}
58276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
58376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    allocate_from(&mmap, copydst, copylen);
58476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
58576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (copylen < o->len) {
58676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		op = split_movelist(copysrc, copylen, op);
58776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		o = *op;
58876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
58976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
59076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    mv = new_movelist(copydst, copysrc, copylen);
59176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n",
59276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    mv->len, mv->src, mv->dst);
59376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    *moves = mv;
59476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    moves = &mv->next;
59576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
59676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    o->src = copydst;
59776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
59876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (copylen > needlen) {
59976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		/* We don't need all the memory we freed up.  Mark it free. */
60076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		if (copysrc < needbase) {
60176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    add_freelist(&mmap, copysrc, needbase - copysrc, SMT_FREE);
60276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    copylen -= (needbase - copysrc);
60376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		}
60476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		if (copylen > needlen) {
60576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    add_freelist(&mmap, copysrc + needlen, copylen - needlen,
60676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman				 SMT_FREE);
60776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    copylen = needlen;
60876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		}
60976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
61076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    reverse = 0;
61176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    goto move_chunk;
61276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
61376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("Cannot find the chunk containing the critical byte\n");
61476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	goto bail;		/* Stuck! */
61576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
61676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanmove_chunk:
61776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	move_chunk(&moves, &mmap, fp, copylen);
61876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
61976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
62076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    /* Finally, append the postcopy chain to the end of the moves list */
62176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    for (op = moves; (o = *op); op = &o->next) ;	/* Locate the end of the list */
62276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    *op = postcopy;
62376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    postcopy = NULL;
62476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
62576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    rv = 0;
62676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanbail:
62776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (mmap)
62876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	syslinux_free_memmap(mmap);
62976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (frags)
63076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	free_movelist(&frags);
63176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (postcopy)
63276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	free_movelist(&postcopy);
63376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    return rv;
63476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
63576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
63676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#ifdef TEST
63776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
63876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#include <stdio.h>
63976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
64076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanint main(int argc, char *argv[])
64176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{
64276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    FILE *f;
64376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    unsigned long d, s, l;
64476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *frags;
64576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist **fep = &frags;
64676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_movelist *mv, *moves;
64776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    struct syslinux_memmap *memmap;
64876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    char line[BUFSIZ];
64976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
65076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    (void)argc;
65176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
65276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    memmap = syslinux_init_memmap();
65376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
65476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    f = fopen(argv[1], "r");
65576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    while (fgets(line, sizeof line, f) != NULL) {
65676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	if (sscanf(line, "%lx %lx %lx", &s, &d, &l) == 3) {
65776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    if (d) {
65876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		if (s == -1UL) {
65976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    syslinux_add_memmap(&memmap, d, l, SMT_ZERO);
66076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		} else {
66176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    mv = new_movelist(d, s, l);
66276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    *fep = mv;
66376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		    fep = &mv->next;
66476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		}
66576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    } else {
66676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman		syslinux_add_memmap(&memmap, s, l, SMT_FREE);
66776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	    }
66876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	}
66976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
67076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    fclose(f);
67176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
67276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    *fep = NULL;
67376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
67476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("Input move list:\n");
67576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    syslinux_dump_movelist(frags);
67676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    dprintf("Input free list:\n");
67776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    syslinux_dump_memmap(memmap);
67876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
67976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    if (syslinux_compute_movelist(&moves, frags, memmap)) {
68076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	printf("Failed to compute a move sequence\n");
68176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	return 1;
68276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    } else {
68376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	dprintf("Final move list:\n");
68476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	syslinux_dump_movelist(moves);
68576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman	return 0;
68676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman    }
68776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman}
68876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman
68976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif /* TEST */
690