A blog on Computer Science, Security, Programming, and more...

Permutation Solution to an Exercise

Written by Matt

Just posting this to link as a solution to: https://blog.svpino.com/2015/05/08/solution-to-problem-5-and-some-other-thoughts-about-this-type-of-questions

Permutations are a fun alternative to recursion. The three possibilities +, -, and (concatenation) in the 8 places between the numbers can easily be represented as an 8-digit number in base 3. Representing that number as an array and incrementing it one by one allows you to iterate through all possibilities without recursion, taking each individual digit in the array as binary function between i+1 and i+2. No allocations!

#include <stdio.h>

void inc_field(int field[8]){


	for (int i = 7; i >= 0; i--){
		switch (field[i]){
			case 4:
			case 3:
				field[i] = (field[i])%3;
				if (i-1 >= 0) field[i-1]++;


int field_get_item(int field[8], int i){

	int left = i+1;

	if (i > 7)
		return left;

		case 0:
			while (i < 8 && field[i] == 0){
				left = left*10 + (i+2);

	return left;

int field_next_pos(int field[8], int i){

	if (field[i] != 0) 
		return i;

	while (i < 8 && field[i] == 0)

	return i;

void print_field(int field[8]){

	for (int i = 0; i < 8; i++){
		putchar(i + '0' + 1);
		if (field[i] == 1)
		if (field[i] == 2)


int main(int argc, char **argv){

	// 0 = nothing, 1 = +, 2 = -
	int field[8] = {0};

	// 3 values per position, 1,2,3,4,5,6,7,8,9 == 8 positions, 3^8 == 6501
	for (int i = 0; i < 6561; i++){

		int hold = 0;
		int j = 0;

		hold = field_get_item(field, j);

		while (j < 8){

			int n = field_next_pos(field, j);
			int right = field_get_item(field, n+1);

				case 1:
					hold += right;
				case 2:
					hold -= right;

			j = field_next_pos(field, n);
			if (j == n) j++;

		if (hold == 100){
			printf(" == %d\n", hold);


	return 0;


123+45-67+8-9 == 100
123+4-5+67-89 == 100
123-45-67+89 == 100
123-4-5-6-7+8-9 == 100
12+3+4+5-6-7+89 == 100
12+3-4+5+67+8+9 == 100
12-3-4+5-6+7+89 == 100
1+23-4+56+7+8+9 == 100
1+23-4+5+6+78-9 == 100
1+2+34-5+67-8+9 == 100
1+2+3-4+5+6+78+9 == 100

FizzBuzz in Vim

Written by Matt

Can you write FizzBuzz using only your editor's macro language? In vim you can. I found out about vim's '-s' option recently, something that will read a file and interpret the bytes as raw key commands. You can create 'strings' that feed into vim and execute macros or any vim command.

As an example, here's a string that generates a FizzBuzz solution inside of vim's buffer - the actual 'program' produced by printf is only 69 bytes! Run the below in a terminal and vim will open with FizzBuzz's output

vim -s <(printf "i1 \x1bqqYp\x01q98@qkqqAFizz\x1b3kq32@qGqqABuzz\x1b5kq19@q:%%s/ $\x0d:%%s/^[0-9]* //g\x0d")

It defines macros to create and increment the integers, then creates a macro to skip lines and add Fizz, does the same for Buzz on line multiples of 3 and 5 respectively, and then uses sed to clean up the output.

Here's the snipped output:

Topic: Programming tags: linux, fun, vim, macros

Factorials Without Recursion or Loops

Written by Matt

I never see this exemplified in any demonstrations of how to compute a factorial, but you can compute a factorial by computing e raised to the natural logarithm of the gamma function (which is an extension of the factorial to the real and complex numbers).

Mathematically it looks as follows:

(1) eln(Γ(n+1))

where e is Euler's Number, n is the argument you would give to the factorial function, and Γ is the gamma function.

The Standard C Math Library has all of these functions, and the log-gamma factorial can be implemented in C/C++ in one line as follows:

long int fac(unsigned long int n) {
  return lround(exp(lgamma(n+1)));

lround() is used just because exp() returns a float, and exp raises e to its argument's power. Make sure to include math.h or cmath for C and C++ respectively.


Writing a Netfilter Linux Kernel Module for 3.x.x Kernels

Written by Matt

The Linux kernel API sure changes a lot. Functions just magically disappear, or they change in subtle ways like a pointer becoming a pointer to a pointer and vice versa - which causes only a warning when compiled but will panic your kernel if you try to load in that module. Thank you, Linux Kernel devs.

Most of the code (or all of the code?) that specifies how to use Netfilter on the internet right now is outdated and no longer works on 3.x.x kernels. It will just not compile or crash your machine if you try to use it. This post contains updated example code that will use Netfilter's kernel-space API to drop all incoming packets - please don't compile and load this module on a remote server, as you will lose access to it completely. Netfilter's hooks have the capability to run well before the regular iptables stages and even SELinux's processing hooks. You are working in kernel space, so you are not limited in the normal sense. Be aware that in kernel-space programming libc is not available.

Note: if this gives you a warning when you try to compile it on your kernel, you should look in your netfilter kernel headers to see whether the function signature is different from your kernel. The kernel code is in /lib/modules/`uname -r`/source - if you have the appropriate headers installed. Depending on your kernel version, the first argument of nk_hook_ex's signature might have to be different. It changed sometime in the middle of 3.x.x's development, the very latest kernels require "const struct nf_hook_ops *ops" instead of "unsigned int" as the first argument to an nf_hookfn.

The Code

The code is fairly simple and terse. Just use it as a base to go off of. Write the following to a file and name it nkmod.c (important).

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/netfilter.h>
#include <linux/netfilter_ipv4.h>

static struct nf_hook_ops hk; 

/* if you get a warning about this function, change the first argument to "const struct nf_hook_ops *ops" - it is basically a copy of the variables fed into 'hk' below */
unsigned int nf_hook_ex(unsigned int hooknum, struct sk_buff *skb, const struct net_device *in, const struct net_device *out, int (*okfn)(struct sk_buff *)){

        if (skb != NULL)
                printk(KERN_INFO "Dropping received packet\n");

        return NF_DROP;

/* Called when module loaded using 'insmod' */
int kmod_init(void){
        /* Just some fancy C to copy an inline struct */
        hk = (struct nf_hook_ops){
                .hook = nf_hook_ex, /* this is important, this variable is of type nf_hookfn - the signature of the function MUST match this type */
                .hooknum = NF_INET_PRE_ROUTING, /* Prerouting is the first netfilter stage */
                .pf = PF_INET, /* Just hook for Internet Packets */
                .priority = NF_IP_PRI_FIRST /* Run this hook before any other hook */

  return 0;

/* Called when module unloaded using 'rmmod' */
void kmod_exit(void){

/* Some standard macros to pass the kernel compile script some information */

Here is the accompanying Makefile - it references nkmod.o and it passes that to the kernel's automatic kbuild makefiles. The file in the directory from where you run "make" must then be called nkmod.c.

obj-m += nkmod.o

        make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

        make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

Just run "make" in the directory that holds both these files. If the build fails, it means you don't have kernel headers installed. If running on a yum based distro, then run "yum install kernel-devel-`uname -r`", on an apt distro run "apt-get install linux-headers-`uname -r`" instead.

Once the module is built, just load it by running "insmod nkmod.ko" as root. All traffic will now be dropped until you unload the module with "rmmod nkmod" - likewise as root. No application will be able to see any packets at all, this hooks the very first stage in the kernel after the network device driver processes the packets on the physical interface.

Please note the use of printk instead of printf - if you use printf you will likely cause a kernel panic. The kernel has its own set of functions for I/O, and printk prints to /var/log/messages, or to journalctl if you use systemd.

That's all there is to it. The definitions for netfilter are in /lib/modules/`uname -r`/source/include/linux/netfilter.h -- open that file and just browse the referenced source. sk_buff, the actual structure that contains the packets, changes ridiculously often and there's not even any point in trying to write a how-to for it, since it will become obsolete within a month at best.

The sk_buff structure is defined in /lib/modules/`uname -r`/source/include/linux/skbuff.h - it is a large structure, but you can look at source of other kernel modules to see what you should reference for your use case.


Linux Memory Allocation and Forcing Memory Release

Written by Matt

The below is a terse explanation of how allocating memory with libc in Linux works. With libc is important, because you can allocate memory in straight assembly by just calling syscall and the below no longer applies. If you are curious as to how, here is an example for 64-bit Linux on x86-64 that allocates a 16MB page. You will need the NASM assembler:

extern printf

section .data

        db 'Current program data segment end address: %llX',0xA,0x00
        db 'Size after brk +0x1000000: %llX',0xA,0x00

section .text

global main
# call brk, store result on stack
mov rax, 12
xor rdi, rdi
push rax

# report end of program break
mov rdi, strQ
mov rsi, rax
call printf

# allocate 16MB of memory by adding 1024*1024*16 to the return of brk
mov rax, 12
pop rdi
add rdi, 0x1000000

# report new program break
mov rdi, strE
mov rsi, rax
call printf

# call exit
mov rax, 60
xor rdi, rdi
Assemble and link with:

nasm -f elf64 -o brk.o brk.s
ld -s -dynamic-linker /lib64/ld-linux-x86-64.so.2 -e main -lc -o brk brk.o
Example run:

$ ./brk       
Current program data segment end address: B73000
Size after brk +0x1000000: 1B73000

Almost all programs, though, regardless of language, use libc calls in Linux to allocate memory. Note that from the kernel's perspective, there is really no difference between the "heap" and the "stack". They are both stored in RAM, obviously, the pages are just tagged differently. You can get and modify the program's stack size with getrlimit() and setrlimit().

Linux's Memory Model

When you allocate memory on Linux, malloc() calls the system call brk(), which tells the kernel to set the "program break", i.e., the end of the program's data segment, which is essentially what determines the size of the "heap". Due to the fact that memory allocation works by pages, even if you free memory using free() it won't really be released unless what you've released is at the end of the program's data segment. In essence, if you free something at the start of the segment, and then malloc it again, libc will simply return that block back to you instead of requesting a new page of memory from the kernel.

Beyond the above mechanics, even if you do free data at the end of the program's segment, it's not guaranteed that said memory will actually be released back to the kernel. Many libc implementations instead often decide to defer that release for performance reasons, so that if you malloc something a short while later it doesn't need to bother the kernel and can just return the block it kept allocated.

Forcing Memory Release

There are times though when you really want to release memory to the OS as soon as possible (such as if you're working on an embedded system with very limited memory), without messing around with brk and sbrk and potentially destroying malloc's internal memory map. For those cases, the library call malloc_trim() does just that, it releases the maximum amount of pages it can if called with the argument 0. It "trims" space at the end of the data segment, and the argument is the amount of space to leave "left" after the last still allocated/in use block. So if called with 0, it forces a release of all memory that is no longer in use.

The only downside is that there is no real guarantee that this is even implemented as it's not a standard library function, and sometimes it's poorly implemented and not thread safe. Using this on a system with large amounts of memory will only serve to make your program slower, but it is a useful function to know when you're working on a system with very limited resources and you want to make sure you don't push the rest of the memory into SWAP, and that your program doesn't accidentally get killed by the OS for having a virtual memory size that's too big.