aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorStefan Bucur <stefanb@zytor.com>2008-08-11 19:22:29 +0300
committerStefan Bucur <stefan@stefan-ubumac.(none)>2009-03-15 10:10:50 +0200
commit9195aa5d71b5593742fcae9957e2e9328717fb12 (patch)
tree92743c40530ba52d78b81040eee1bb1110a38180
parentfac2992f2848ce2a630ba03f3a9f43d5928297ae (diff)
downloadsyslinux-elf-9195aa5d71b5593742fcae9957e2e9328717fb12.tar.gz
syslinux-elf-9195aa5d71b5593742fcae9957e2e9328717fb12.tar.xz
syslinux-elf-9195aa5d71b5593742fcae9957e2e9328717fb12.zip
Created a simple quick sort module.
-rw-r--r--com32/elflink/modules/Makefile5
-rw-r--r--com32/elflink/modules/hello.c39
-rw-r--r--com32/elflink/modules/sort.c75
-rw-r--r--com32/elflink/modules/sort.h19
-rw-r--r--com32/lib/Makefile1
-rw-r--r--com32/lib/sys/module/common.c2
-rw-r--r--com32/lib/sys/module/common.h2
-rw-r--r--com32/lib/sys/module/elf_module.c2
-rw-r--r--com32/lib/sys/module/shallow_module.c2
9 files changed, 140 insertions, 7 deletions
diff --git a/com32/elflink/modules/Makefile b/com32/elflink/modules/Makefile
index fc319b03..9eeef1a9 100644
--- a/com32/elflink/modules/Makefile
+++ b/com32/elflink/modules/Makefile
@@ -51,7 +51,7 @@ AUXDIR = $(DATADIR)/syslinux
INCDIR = /usr/include
COM32DIR = $(AUXDIR)/com32
-MODULES = hello.dyn
+MODULES = hello.dyn sort.dyn
TESTFILES =
@@ -83,6 +83,9 @@ all: $(MODULES) $(TESTFILES)
hello.dyn : hello.o $(LIBS)
$(LD) $(LDFLAGS) -o $@ $^
+
+sort.dyn : sort.o $(LIBS)
+ $(LD) $(LDFLAGS) -o $@ $^
tidy dist:
rm -f *.o *.lo *.a *.lst .*.d
diff --git a/com32/elflink/modules/hello.c b/com32/elflink/modules/hello.c
index d1054a1f..2386ecb3 100644
--- a/com32/elflink/modules/hello.c
+++ b/com32/elflink/modules/hello.c
@@ -1,14 +1,49 @@
/*
- * The first prototype of an ELF module, inspired from the Linux kernel
- * module system.
+ * hello.c - A simple ELF module that sorts a couple of numbers
+ *
+ * Created on: Aug 11, 2008
+ * Author: Stefan Bucur <stefanb@zytor.com>
*/
#include <stdio.h>
+#include <stdlib.h>
#include <sys/module.h>
+#include "sort.h"
+
+
+#define NUM_COUNT 10
+#define MAX_NUM 100
+
static int hello_init(void) {
+ int *nums = NULL;
+ int i;
+
printf("Hello, world, from 0x%08X!\n", (unsigned int)&hello_init);
+
+ nums = malloc(NUM_COUNT*sizeof(int));
+
+ for (i = 0; i < NUM_COUNT; i++) {
+ nums[i] = rand() % MAX_NUM;
+ }
+
+ printf("Numbers before sort: ");
+ for (i = 0; i < NUM_COUNT; i++) {
+ printf("%d ", nums[i]);
+ }
+ printf("\n");
+
+ quick_sort(nums, NUM_COUNT);
+
+ printf("Numbers after sort: ");
+ for (i = 0; i < NUM_COUNT; i++) {
+ printf("%d ", nums[i]);
+ }
+ printf("\n");
+
+ free(nums);
+
return 0;
}
diff --git a/com32/elflink/modules/sort.c b/com32/elflink/modules/sort.c
new file mode 100644
index 00000000..a6f854d9
--- /dev/null
+++ b/com32/elflink/modules/sort.c
@@ -0,0 +1,75 @@
+/*
+ * sort.c - Sample ELF module providing a quick sort function
+ *
+ * Created on: Aug 11, 2008
+ * Author: Stefan Bucur <stefanb@zytor.com>
+ */
+
+#include <stdlib.h>
+#include <sys/module.h>
+
+/**
+ * sort_init - Module entry point.
+ */
+static int sort_init() {
+ return 0; // Nothing to do; return success
+}
+
+
+static inline void swap(int *x, int *y) {
+ int tmp;
+ tmp = *x;
+ *x = *y;
+ *y = tmp;
+}
+
+static inline int randint(int l, int u) {
+ return l + (rand() % (u-l+1));
+}
+
+/**
+ * quick_sort_range - A small and efficient version of quicksort.
+ * @nums: The numbers to sort
+ * @l: The lower index in the vector (inclusive)
+ * @u: The upper index in the vector (inclusive)
+ *
+ * The implementation is taken from "Beautiful Code", by O'Reilly, the
+ * book students received from Google as a gift for their acceptance
+ * in the GSoC 2008 program. The code belongs to Jon Bentley, who
+ * wrote the third chapter of the book. Since ELF modules were written
+ * as part of this program, the author of the module considered
+ * the book had to be put at some use. :)
+ */
+static void quick_sort_range(int *nums, int l, int u) {
+ int i, m;
+ if (l >= u) return;
+
+ swap(&nums[l], &nums[randint(l, u)]);
+
+ m = 1;
+ for (i = l+1; i <= u; i++) {
+ if (nums[i] < nums[l])
+ swap(&nums[++m], &nums[i]);
+ }
+
+ swap(&nums[l], &nums[m]);
+
+ quick_sort_range(nums, l, m-1);
+ quick_sort_range(nums, m+1, u);
+}
+
+
+void quick_sort(int *nums, int count) {
+ quick_sort_range(nums, 0, count-1);
+}
+
+/**
+ * sort_exit - Module exit point.
+ */
+static void sort_exit() {
+ // Nothing to do
+}
+
+// Define entry and exit points.
+MODULE_INIT(sort_init);
+MODULE_EXIT(sort_exit);
diff --git a/com32/elflink/modules/sort.h b/com32/elflink/modules/sort.h
new file mode 100644
index 00000000..35b8f5a6
--- /dev/null
+++ b/com32/elflink/modules/sort.h
@@ -0,0 +1,19 @@
+/*
+ * sort.h - Quick sort module API definitions
+ *
+ * Created on: Aug 11, 2008
+ * Author: Stefan Bucur <stefanb@zytor.com>
+ */
+
+#ifndef SORT_H_
+#define SORT_H_
+
+/**
+ * quick_sort - In place sort of an array of numbers.
+ * @nums: Pointer to the array
+ * @count: The number count in the array
+ */
+extern void quick_sort(int *nums, int count);
+
+
+#endif /* SORT_H_ */
diff --git a/com32/lib/Makefile b/com32/lib/Makefile
index 44064faa..87dd7a9b 100644
--- a/com32/lib/Makefile
+++ b/com32/lib/Makefile
@@ -180,6 +180,7 @@ libcom32.a : $(LIBOBJS)
$(AR) cq $@ $^
$(RANLIB) $@
+libcom32min.a : CFLAGS += -DELF_DEBUG
libcom32min.a : $(MINLIBOBJS)
rm -f $@
$(AR) cq $@ $^
diff --git a/com32/lib/sys/module/common.c b/com32/lib/sys/module/common.c
index 88fa4595..7634cf30 100644
--- a/com32/lib/sys/module/common.c
+++ b/com32/lib/sys/module/common.c
@@ -2,7 +2,7 @@
* common.c
*
* Created on: Aug 11, 2008
- * Author: Stefan Bucur <stefanb[at]zytor.com>
+ * Author: Stefan Bucur <stefanb@zytor.com>
*/
#include <stdio.h>
diff --git a/com32/lib/sys/module/common.h b/com32/lib/sys/module/common.h
index a13027a6..9b13afca 100644
--- a/com32/lib/sys/module/common.h
+++ b/com32/lib/sys/module/common.h
@@ -2,7 +2,7 @@
* common.h - Common internal operations performed by the module subsystem
*
* Created on: Aug 11, 2008
- * Author: Stefan Bucur <stefanb[at]zytor.com>
+ * Author: Stefan Bucur <stefanb@zytor.com>
*/
#ifndef COMMON_H_
diff --git a/com32/lib/sys/module/elf_module.c b/com32/lib/sys/module/elf_module.c
index 82f1be89..669c2533 100644
--- a/com32/lib/sys/module/elf_module.c
+++ b/com32/lib/sys/module/elf_module.c
@@ -2,7 +2,7 @@
* elf_module.c
*
* Created on: Aug 11, 2008
- * Author: Stefan Bucur <stefanb[at]zytor.com>
+ * Author: Stefan Bucur <stefanb@zytor.com>
*/
diff --git a/com32/lib/sys/module/shallow_module.c b/com32/lib/sys/module/shallow_module.c
index c4a9ff15..1b76aaae 100644
--- a/com32/lib/sys/module/shallow_module.c
+++ b/com32/lib/sys/module/shallow_module.c
@@ -2,7 +2,7 @@
* shallow_module.c
*
* Created on: Aug 11, 2008
- * Author: Stefan Bucur <stefanb[at]zytor.com>
+ * Author: Stefan Bucur <stefanb@zytor.com>
*/
#include "common.h"