make a bootable BIOS

includes source from kvm-unit-tests

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

18 files changed, 683 insertions, 78 deletions

diff --git a/Makefile b/Makefile
index 0fb6c95..2e8a142 100644
--- a/Makefile
+++ b/Makefile
@@ -1,11 +1,14 @@
 obj16-y = e820.o int10.o int15.o
-obj-y = $(obj16-y) entry.o
+obj-y = $(obj16-y) entry.o main.o string.o printf.o cstart.o
 all-y = bios.bin
 
+CFLAGS := -O2 -Wall -g
+
 BIOS_CFLAGS += -m32
 BIOS_CFLAGS += -march=i386
 BIOS_CFLAGS += -mregparm=3
-BIOS_CFLAGS += -fno-stack-protector
+BIOS_CFLAGS += -fno-stack-protector -fno-delete-null-pointer-checks
+BIOS_CFLAGS += -ffreestanding
 BIOS_CFLAGS += -Iinclude
 $(obj16-y): BIOS_CFLAGS += -include code16gcc.h
 
@@ -17,11 +20,11 @@ all: $(all-y)
 %.o: %.S
 	$(CC) $(CFLAGS) $(BIOS_CFLAGS) -c -s $< -o $@
 
-bios.bin.elf: $(obj-y) rom.ld.S
-	$(LD) -T rom.ld.S -o bios.bin.elf $(obj-y)
+bios.bin.elf: $(obj-y) flat.lds
+	$(LD) -T flat.lds -o bios.bin.elf $(obj-y)
 
 bios.bin: bios.bin.elf
 	objcopy -O binary bios.bin.elf bios.bin
 
 clean:
-	rm $(obj-y) $(all-y) bios.bin.elf
+	rm -f $(obj-y) $(all-y) bios.bin.elf
diff --git a/cstart.S b/cstart.S
new file mode 100644
index 0000000..5ca61c8
--- /dev/null
+++ b/cstart.S
@@ -0,0 +1,38 @@
+.code16gcc
+#include "assembly.h"
+.section .init
+ENTRY(pm_entry)
+	xor %ax, %ax
+	mov %ax, %ds
+	mov %ax, %es
+	mov %ax, %ss
+	mov $0x7c00, %sp
+
+        mov %cr0, %eax
+        or $1, %eax
+        mov %eax, %cr0
+        lgdtl %cs:0xff80 + gdt32_descr - pm_entry
+        ljmpl $8, $0xffffff80 + 2f - pm_entry
+2:
+	.code32
+	mov $16, %ax
+	mov %ax, %ds
+	mov %ax, %es
+	mov %ax, %ss
+	ljmp $8, $0xffff0000
+
+gdt32:
+        .quad 0
+        .quad 0x00cf9b000000ffff // flat 32-bit code segment
+        .quad 0x00cf93000000ffff // flat 32-bit data segment
+gdt32_end:
+
+gdt32_descr:
+        .word gdt32_end - gdt32 - 1
+        .long 0xffffff80 + gdt32 - pm_entry
+ENTRY_END(pm_entry)
+
+	.code16gcc
+	.section .resetvector
+	jmp	pm_entry
+
diff --git a/e820.c b/e820.c
index 4eab157..6271353 100644
--- a/e820.c
+++ b/e820.c
@@ -27,35 +27,32 @@ static inline uint32_t rdfs32(unsigned long addr)
 	return v;
 }
 
+struct e820map e820;
+
 bioscall void e820_query_map(struct biosregs *regs)
 {
-	struct e820map *e820;
 	uint32_t map_size;
 	uint16_t fs_seg;
 	uint32_t ndx;
 
-	e820		= (struct e820map *)E820_MAP_START;
-	fs_seg		= flat_to_seg16(E820_MAP_START);
+	fs_seg		= flat_to_seg16((uintptr_t) &e820);
 	set_fs(fs_seg);
 
 	ndx		= regs->ebx;
 
-	map_size	= rdfs32(flat_to_off16((uint32_t)&e820->nr_map, fs_seg));
+	map_size	= rdfs32(flat_to_off16((uintptr_t) &e820.nr_map));
 
 	if (ndx < map_size) {
 		uint32_t start;
 		unsigned int i;
 		uint8_t *p;
 
-		fs_seg	= flat_to_seg16(E820_MAP_START);
-		set_fs(fs_seg);
-
-		start	= (uint32_t)&e820->map[ndx];
+		start	= flat_to_off16((uintptr_t)&e820.map[ndx]);
 
 		p	= (void *) regs->edi;
 
 		for (i = 0; i < sizeof(struct e820entry); i++)
-			*p++	= rdfs8(flat_to_off16(start + i, fs_seg));
+			*p++	= rdfs8(start + i);
 	}
 
 	regs->eax	= SMAP;
diff --git a/entry.S b/entry.S
index a192c7d..89fa51e 100644
--- a/entry.S
+++ b/entry.S
@@ -84,12 +84,3 @@ ENTRY(bios_int15)
 
 	IRET
 ENTRY_END(bios_int15)
-
-ENTRY(real_entry)
-	cli
-	hlt
-ENTRY_END(real_entry)
-
-	ORG(fff0)
-	jmp	real_entry
-
diff --git a/flat.lds b/flat.lds
new file mode 100644
index 0000000..d12b835
--- /dev/null
+++ b/flat.lds
@@ -0,0 +1,24 @@
+OUTPUT_ARCH(i386)
+
+SECTIONS
+{
+    . = 1024K - 64K;
+    .text : { *(.text.startup) *(.text) *(.text.*) }
+    . = ALIGN(4K);
+    .data : { *(.data) }
+    . = ALIGN(16);
+    .rodata : { *(.rodata) }
+    . = ALIGN(16);
+    .bss : { *(.bss) }
+    . = ALIGN(4K);
+    . = 1024K - 128;
+    .init : {
+	*(.init);
+	. = 128 - 16;
+        *(.resetvector);
+	. = 128;
+    }
+}
+
+ENTRY(main)
+
diff --git a/include/assembly.h b/include/assembly.h
index 3601024..6965583 100644
--- a/include/assembly.h
+++ b/include/assembly.h
@@ -3,6 +3,10 @@
 
 #define __ASSEMBLY__
 
+#define BIOS2FLAT(x)	((x) - _start + 0xf0000)
+#define BIOS2FLATROM(x)	((x) - _start + 0xffff0000)
+_start = 0
+
 #define ORG(x)	\
 	.section .fixedaddr._##x
 
diff --git a/include/bios.h b/include/bios.h
index 153c887..22a912a 100644
--- a/include/bios.h
+++ b/include/bios.h
@@ -4,32 +4,6 @@
 #include <inttypes.h>
 
 /*
- * X86-32 Memory Map (typical)
- *					start      end
- * Real Mode Interrupt Vector Table	0x00000000 0x000003FF
- * BDA area				0x00000400 0x000004FF
- * Conventional Low Memory		0x00000500 0x0009FBFF
- * EBDA area				0x0009FC00 0x0009FFFF
- * VIDEO RAM				0x000A0000 0x000BFFFF
- * VIDEO ROM (BIOS)			0x000C0000 0x000C7FFF
- * ROMs & unus. space (mapped hw & misc)0x000C8000 0x000EFFFF 160 KiB (typically)
- * Motherboard BIOS			0x000F0000 0x000FFFFF
- * Extended Memory			0x00100000 0xFEBFFFFF
- * Reserved (configs, ACPI, PnP, etc)	0xFEC00000 0xFFFFFFFF
- */
-
-#define REAL_MODE_IVT_BEGIN		0x00000000
-#define REAL_MODE_IVT_END		0x000003ff
-
-#define BDA_START			0x00000400
-#define BDA_END				0x000004ff
-
-#define EBDA_START			0x0009fc00
-#define EBDA_END			0x0009ffff
-
-#define E820_MAP_START			EBDA_START
-
-/*
  * When interfacing with assembler code we need to be sure how
  * arguments are passed in real mode.
  */
@@ -37,8 +11,6 @@
 
 #ifndef __ASSEMBLER__
 
-#include <linux/types.h>
-
 struct biosregs {
 	uint32_t			eax;
 	uint32_t			ebx;
@@ -59,6 +31,14 @@ extern bioscall void int10_handler(struct biosregs *regs);
 extern bioscall void int15_handler(struct biosregs *regs);
 extern bioscall void e820_query_map(struct biosregs *regs);
 
+extern struct e820map e820;
+
+static inline void __attribute__((noreturn)) panic(void)
+{
+	asm volatile("cli; hlt");
+	for(;;);
+}
+
 #endif
 
 #endif /* BIOS_H_ */
diff --git a/include/ioport.h b/include/ioport.h
new file mode 100644
index 0000000..bbec982
--- /dev/null
+++ b/include/ioport.h
@@ -0,0 +1,50 @@
+#ifndef _IOPORT_H
+#define _IOPORT_H 1
+
+static inline void outsb(unsigned short port, void *buf, int len)
+{
+	asm volatile("rep outsb %%ds:(%0), %3" : "+S" (buf), "+c" (len) : "m"(buf), "Nd"(port), "0" (buf), "1" (len));
+}
+
+static inline void insb(void *buf, unsigned short port, int len)
+{
+	asm volatile("rep insb %3, %%es:(%0)" : "+D" (buf), "+c" (len), "=m"(buf) : "Nd"(port), "0" (buf), "1" (len));
+}
+
+static inline unsigned char inb(unsigned short port)
+{
+	unsigned char val;
+	asm volatile("inb %1, %0" : "=a"(val) : "Nd"(port));
+	return val;
+}
+
+static inline unsigned short inw(unsigned short port)
+{
+	unsigned short val;
+	asm volatile("inw %1, %0" : "=a"(val) : "Nd"(port));
+	return val;
+}
+
+static inline unsigned inl(unsigned short port)
+{
+	unsigned val;
+	asm volatile("inl %1, %0" : "=a"(val) : "Nd"(port));
+	return val;
+}
+
+static inline void outb(unsigned short port, unsigned char val)
+{
+	asm volatile("outb %0, %1" : : "a"(val), "Nd"(port));
+}
+
+static inline void outw(unsigned short port, unsigned short val)
+{
+	asm volatile("outw %0, %1" : : "a"(val), "Nd"(port));
+}
+
+static inline void outl(unsigned short port, unsigned val)
+{
+	asm volatile("outl %0, %1" : : "a"(val), "Nd"(port));
+}
+
+#endif
diff --git a/include/pci.h b/include/pci.h
new file mode 100644
index 0000000..e6b445c
--- /dev/null
+++ b/include/pci.h
@@ -0,0 +1,44 @@
+#ifndef _PCI_H
+#define _PCI_H
+
+#include "ioport.h"
+
+static inline void pci_config_writel(uint16_t bdf, uint32_t addr, uint32_t val)
+{
+	outl(0xcf8, 0x80000000 | (bdf << 8) | (addr & 0xfc));
+	outl(0xcfc, val);
+}
+
+void pci_config_writew(uint16_t bdf, uint32_t addr, uint16_t val)
+{
+	outl(0xcf8, 0x80000000 | (bdf << 8) | (addr & 0xfc));
+	outw(0xcfc | (addr & 2), val);
+}
+
+void pci_config_writeb(uint16_t bdf, uint32_t addr, uint8_t val)
+{
+	outl(0xcf8, 0x80000000 | (bdf << 8) | (addr & 0xfc));
+	outb(0xcfc | (addr & 3), val);
+}
+
+uint32_t pci_config_readl(uint16_t bdf, uint32_t addr)
+{
+	outl(0xcf8, 0x80000000 | (bdf << 8) | (addr & 0xfc));
+	return inl(0xcfc);
+}
+
+uint16_t pci_config_readw(uint16_t bdf, uint32_t addr)
+{
+	outl(0xcf8, 0x80000000 | (bdf << 8) | (addr & 0xfc));
+	return inw(0xcfc | (addr & 2));
+}
+
+uint8_t pci_config_readb(uint16_t bdf, uint32_t addr)
+{
+	outl(0xcf8, 0x80000000 | (bdf << 8) | (addr & 0xfc));
+	return inb(0xcfc | (addr & 3));
+}
+
+#define PCI_VENDOR_ID 0
+
+#endif
diff --git a/include/segment.h b/include/segment.h
index 694eb4b..7b68706 100644
--- a/include/segment.h
+++ b/include/segment.h
@@ -8,12 +8,12 @@ static inline uint32_t segment_to_flat(uint16_t selector, uint16_t offset)
 
 static inline uint16_t flat_to_seg16(uint32_t address)
 {
-	return address >> 4;
+	return (address >> 4) & 0xf000;
 }
 
-static inline uint16_t flat_to_off16(uint32_t address, uint32_t segment)
+static inline uint16_t flat_to_off16(uint32_t address)
 {
-	return address - (segment << 4);
+	return address & 65535;
 }
 
 #endif /* KVM_SEGMENT_H */
diff --git a/include/stdio.h b/include/stdio.h
new file mode 100644
index 0000000..c154933
--- /dev/null
+++ b/include/stdio.h
@@ -0,0 +1,11 @@
+#ifndef BIOS_STDIO_H
+#define BIOS_STDIO_H 1
+
+#include <stdarg.h>
+
+extern int puts(const char *s);
+extern int printf(const char *fmt, ...);
+extern int snprintf(char *buf, int size, const char *fmt, ...);
+extern int vsnprintf(char *buf, int size, const char *fmt, va_list va);
+
+#endif
diff --git a/include/stdlib.h b/include/stdlib.h
new file mode 100644
index 0000000..8de2f31
--- /dev/null
+++ b/include/stdlib.h
@@ -0,0 +1,6 @@
+#ifndef BIOS_STDLIB_H
+#define BIOS_STDLIB_H 1
+
+extern long atol(const char *ptr);
+
+#endif
diff --git a/include/string.h b/include/string.h
new file mode 100644
index 0000000..962b07e
--- /dev/null
+++ b/include/string.h
@@ -0,0 +1,18 @@
+#ifndef _STRING_H
+#define _STRING_H
+
+#include <stddef.h>
+
+unsigned long strlen(const char *buf);
+char *strcat(char *dest, const char *src);
+char *strcpy(char *dest, const char *src);
+int strcmp(const char *a, const char *b);
+char *strchr(const char *s, int c);
+char *strstr(const char *s1, const char *s2);
+void *memset(void *s, int c, size_t n);
+void *memcpy(void *dest, const void *src, size_t n);
+int memcmp(const void *s1, const void *s2, size_t n);
+void *memmove(void *dest, const void *src, size_t n);
+void *memchr(const void *s, int c, size_t n);
+
+#endif
diff --git a/int10.c b/int10.c
index 9d9604c..0e506cc 100644
--- a/int10.c
+++ b/int10.c
@@ -1,10 +1,6 @@
 #include "bios.h"
 #include "segment.h"
-
-static inline void outb(unsigned short port, unsigned char val)
-{
-	asm volatile("outb %0, %1" : : "a"(val), "Nd"(port));
-}
+#include "ioport.h"
 
 /*
  * It's probably much more useful to make this print to the serial
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..eeb21fd
--- /dev/null
+++ b/main.c
@@ -0,0 +1,49 @@
+#include "bios.h"
+#include "pci.h"
+#include "string.h"
+
+#define PCI_VENDOR_ID_INTEL		0x8086
+#define PCI_DEVICE_ID_INTEL_82441	0x1237
+#define PCI_DEVICE_ID_INTEL_Q35_MCH     0x29c0
+
+#define I440FX_PAM0                     0x59
+#define Q35_HOST_BRIDGE_PAM0            0x90
+
+static void make_bios_writable(void)
+{
+	const int bdf = 0;
+	const uint8_t *bios_start = (uint8_t *)0xffff0000;
+	uint8_t *low_start = (uint8_t *)0xf0000;
+	int pambase;
+
+        uint32_t id = pci_config_readl(bdf, 0);
+        if (id == (PCI_VENDOR_ID_INTEL | (PCI_DEVICE_ID_INTEL_82441 << 16)))
+		pambase = I440FX_PAM0;
+        else if (id == (PCI_VENDOR_ID_INTEL | (PCI_DEVICE_ID_INTEL_Q35_MCH << 16)))
+		pambase = Q35_HOST_BRIDGE_PAM0;
+        else
+		panic();
+
+	// Make ram from 0xc0000-0xf0000 read-write
+	int i;
+	for (i=0; i<6; i++) {
+		int pam = pambase + 1 + i;
+		pci_config_writeb(bdf, pam, 0x33);
+	}
+
+	// Make ram from 0xf0000-0x100000 read-write and shadow BIOS
+	// We're still running from 0xffff0000
+	pci_config_writeb(bdf, pambase, 0x30);
+	memcpy(low_start, bios_start, 0x10000);
+}
+
+
+int main(void)
+{
+	make_bios_writable();
+	// extract_acpi();
+	// extract_smbios();
+	// extract_kernel();
+	// boot_linux();
+	panic();
+}
diff --git a/printf.c b/printf.c
new file mode 100644
index 0000000..a171d24
--- /dev/null
+++ b/printf.c
@@ -0,0 +1,256 @@
+#include "bios.h"
+#include "stdio.h"
+#include "string.h"
+#include "stdlib.h"
+#include "ioport.h"
+
+typedef struct pstream {
+    char *buffer;
+    int remain;
+    int added;
+} pstream_t;
+
+typedef struct strprops {
+    char pad;
+    int npad;
+} strprops_t;
+
+static void addchar(pstream_t *p, char c)
+{
+    if (p->remain) {
+	*p->buffer++ = c;
+	--p->remain;
+    }
+    ++p->added;
+}
+
+int puts(const char *c)
+{
+    int n = 0;
+    while (c[n])
+        outb(0x3f8, c[n++]);
+    return n;
+}
+
+void print_str(pstream_t *p, const char *s, strprops_t props)
+{
+    const char *s_orig = s;
+    int npad = props.npad;
+
+    if (npad > 0) {
+	npad -= strlen(s_orig);
+	while (npad > 0) {
+	    addchar(p, props.pad);
+	    --npad;
+	}
+    }
+
+    while (*s)
+	addchar(p, *s++);
+
+    if (npad < 0) {
+	props.pad = ' '; /* ignore '0' flag with '-' flag */
+	npad += strlen(s_orig);
+	while (npad < 0) {
+	    addchar(p, props.pad);
+	    ++npad;
+	}
+    }
+}
+
+static char digits[16] = "0123456789abcdef";
+
+void print_int(pstream_t *ps, long n, int base, strprops_t props)
+{
+    char buf[sizeof(long) * 3 + 2], *p = buf;
+    int s = 0, i;
+
+    if (n < 0) {
+	n = -n;
+	s = 1;
+    }
+
+    while (n) {
+	*p++ = digits[n % base];
+	n /= base;
+    }
+
+    if (s)
+	*p++ = '-';
+
+    if (p == buf)
+	*p++ = '0';
+
+    for (i = 0; i < (p - buf) / 2; ++i) {
+	char tmp;
+
+	tmp = buf[i];
+	buf[i] = p[-1-i];
+	p[-1-i] = tmp;
+    }
+
+    *p = 0;
+
+    print_str(ps, buf, props);
+}
+
+void print_unsigned(pstream_t *ps, unsigned long n, int base,
+		    strprops_t props)
+{
+    char buf[sizeof(long) * 3 + 1], *p = buf;
+    int i;
+
+    while (n) {
+	*p++ = digits[n % base];
+	n /= base;
+    }
+
+    if (p == buf)
+	*p++ = '0';
+
+    for (i = 0; i < (p - buf) / 2; ++i) {
+	char tmp;
+
+	tmp = buf[i];
+	buf[i] = p[-1-i];
+	p[-1-i] = tmp;
+    }
+
+    *p = 0;
+
+    print_str(ps, buf, props);
+}
+
+static int fmtnum(const char **fmt)
+{
+    const char *f = *fmt;
+    int len = 0, num;
+
+    if (*f == '-')
+	++f, ++len;
+
+    while (*f >= '0' && *f <= '9')
+	++f, ++len;
+
+    num = atol(*fmt);
+    *fmt += len;
+    return num;
+}
+
+int vsnprintf(char *buf, int size, const char *fmt, va_list va)
+{
+    pstream_t s;
+
+    s.buffer = buf;
+    s.remain = size - 1;
+    s.added = 0;
+    while (*fmt) {
+	char f = *fmt++;
+	int nlong = 0;
+	strprops_t props;
+	memset(&props, 0, sizeof(props));
+	props.pad = ' ';
+
+	if (f != '%') {
+	    addchar(&s, f);
+	    continue;
+	}
+    morefmt:
+	f = *fmt++;
+	do {
+	if (f == '%') {
+	    addchar(&s, '%');
+	    break;
+	}
+	if (f == 'c') {
+            addchar(&s, va_arg(va, int));
+	    break;
+	}
+	if (f == '\0') {
+	    --fmt;
+	    break;
+	}
+	if (f == '0') {
+	    props.pad = '0';
+	    ++fmt;
+	    /* fall through */
+	}
+	if ((f >= '1' && f <= '9') || f == '-') {
+	    --fmt;
+	    props.npad = fmtnum(&fmt);
+	    goto morefmt;
+	}
+	if (f == 'l') {
+	    ++nlong;
+	    goto morefmt;
+	}
+	if (f == 'd') {
+	    switch (nlong) {
+	    case 0:
+		print_int(&s, va_arg(va, int), 10, props);
+		break;
+	    case 1:
+		print_int(&s, va_arg(va, long), 10, props);
+		break;
+	    default:
+		panic();
+		break;
+	    }
+	    break;
+	}
+	if (f == 'x') {
+	    switch (nlong) {
+	    case 0:
+		print_unsigned(&s, va_arg(va, unsigned), 16, props);
+		break;
+	    case 1:
+		print_unsigned(&s, va_arg(va, unsigned long), 16, props);
+		break;
+	    default:
+		panic();
+		break;
+	    }
+	    break;
+	}
+	if (f == 'p') {
+	    print_str(&s, "0x", props);
+	    print_unsigned(&s, (unsigned long)va_arg(va, void *), 16, props);
+	    break;
+	}
+	if (f == 's') {
+	    print_str(&s, va_arg(va, const char *), props);
+	    break;
+	}
+    	addchar(&s, f);
+    	break;
+	} while(0);
+    }
+    *s.buffer = 0;
+    ++s.added;
+    return s.added;
+}
+
+
+int snprintf(char *buf, int size, const char *fmt, ...)
+{
+    va_list va;
+    int r;
+
+    va_start(va, fmt);
+    r = vsnprintf(buf, size, fmt, va);
+    va_end(va);
+    return r;
+}
+
+int printf(const char *fmt, ...)
+{
+    va_list va;
+    char buf[2000];
+    int r;
+
+    va_start(va, fmt);
+    r = vsnprintf(buf, sizeof buf, fmt, va);
+    va_end(va);
+    puts(buf);
+    return r;
+}
diff --git a/rom.ld.S b/rom.ld.S
deleted file mode 100644
index 04f2ff9..0000000
--- a/rom.ld.S
+++ /dev/null
@@ -1,19 +0,0 @@
-OUTPUT_FORMAT("elf32-i386", "elf32-i386", "elf32-i386")
-OUTPUT_ARCH(i386)
-
-SECTIONS {
-	.text 0	: {
-		*(.text)
-		. = 0xfff0 ;
-		*(.fixedaddr._fff0)
-		. = 0x10000 ;
-	}
-
-	/DISCARD/ : {
-		*(.debug*)
-		*(.data)
-		*(.bss)
-		*(.eh_frame*)
-	}
-}
-
diff --git a/string.c b/string.c
new file mode 100644
index 0000000..3029b9f
--- /dev/null
+++ b/string.c
@@ -0,0 +1,157 @@
+#include "string.h"
+
+unsigned long strlen(const char *buf)
+{
+    unsigned long len = 0;
+
+    while (*buf++)
+	++len;
+    return len;
+}
+
+char *strcat(char *dest, const char *src)
+{
+    char *p = dest;
+
+    while (*p)
+	++p;
+    while ((*p++ = *src++) != 0)
+	;
+    return dest;
+}
+
+char *strcpy(char *dest, const char *src)
+{
+    *dest = 0;
+    return strcat(dest, src);
+}
+
+int strcmp(const char *a, const char *b)
+{
+    while (*a == *b) {
+	if (*a == '\0') {
+	    break;
+	}
+	++a, ++b;
+    }
+    return *a - *b;
+}
+
+char *strchr(const char *s, int c)
+{
+    while (*s != (char)c)
+	if (*s++ == '\0')
+	    return NULL;
+    return (char *)s;
+}
+
+char *strstr(const char *s1, const char *s2)
+{
+    size_t l1, l2;
+
+    l2 = strlen(s2);
+    if (!l2)
+	return (char *)s1;
+    l1 = strlen(s1);
+    while (l1 >= l2) {
+	l1--;
+	if (!memcmp(s1, s2, l2))
+	    return (char *)s1;
+	s1++;
+    }
+    return NULL;
+}
+
+void *memset(void *s, int c, size_t n)
+{
+    size_t i;
+    char *a = s;
+
+    for (i = 0; i < n; ++i)
+        a[i] = c;
+
+    return s;
+}
+
+void *memcpy(void *dest, const void *src, size_t n)
+{
+    size_t i;
+    char *a = dest;
+    const char *b = src;
+
+    for (i = 0; i < n; ++i)
+        a[i] = b[i];
+
+    return dest;
+}
+
+int memcmp(const void *s1, const void *s2, size_t n)
+{
+    const unsigned char *a = s1, *b = s2;
+    int ret = 0;
+
+    while (n--) {
+	ret = *a - *b;
+	if (ret)
+	    break;
+	++a, ++b;
+    }
+    return ret;
+}
+
+void *memmove(void *dest, const void *src, size_t n)
+{
+    const unsigned char *s = src;
+    unsigned char *d = dest;
+
+    if (d <= s) {
+	while (n--)
+	    *d++ = *s++;
+    } else {
+	d += n, s += n;
+	while (n--)
+	    *--d = *--s;
+    }
+    return dest;
+}
+
+void *memchr(const void *s, int c, size_t n)
+{
+    const unsigned char *str = s, chr = (unsigned char)c;
+
+    while (n--)
+	if (*str++ == chr)
+	    return (void *)(str - 1);
+    return NULL;
+}
+
+long atol(const char *ptr)
+{
+    long acc = 0;
+    const char *s = ptr;
+    int neg, c;
+
+    while (*s == ' ' || *s == '\t')
+        s++;
+    if (*s == '-'){
+        neg = 1;
+        s++;
+    } else {
+        neg = 0;
+        if (*s == '+')
+            s++;
+    }
+
+    while (*s) {
+        if (*s < '0' || *s > '9')
+            break;
+        c = *s - '0';
+        acc = acc * 10 + c;
+        s++;
+    }
+
+    if (neg)
+        acc = -acc;
+
+    return acc;
+}