laszlo.nu

Simple linked list (C) for OSP lab

A simple linked list (FIFO-queue) for future generations ;) Get the source.

/*
  Description: Very simple single linked list. Intended for use in the OSP lab
  at Chalmers. In the OS course at Chalmers, you are allowed and even
  encouraged to use an existing linked list instead of implementing your own -
  just remember to add a reference (or else it's cheating!).

  Author: André Laszlo <andre@laszlo.nu>
 */

#include <stdlib.h>
#include <stdio.h>

typedef struct node_s {
  void *data;
  struct node_s *next;
} NODE;

typedef struct list_s {
  NODE *first;
  NODE *last;
  int length;
} LIST;

/* Create a new list */
LIST* new_list()
{
  LIST *l;
  if (!(l=malloc(sizeof(LIST))))
    return NULL;

  l->length = 0;
  l->first = NULL;
  l->last = NULL;
  return l;
}

/* Create a new node that can be inserted into the list */
NODE* new_node(void *data)
{
  NODE *n;
  if (!(n=malloc(sizeof(NODE))))
    return NULL;
  n->next = NULL;
  n->data = data;
  return n;
}

/* Insert element at the end of the list */
void append(LIST *l, void *data)
{
  NODE *n = new_node(data);
  if (l->length == 0) {
    l->first = n;
    l->last = n;
  } else {
    l->last->next = n;
    l->last = n;
  }

  l->length++;
}

/* remove from head of list and return data */
void* pop(LIST *l)
{
  if (l->length == 0) {
    return NULL;
  } else if (l->length == 1) {
    void *data = l->first->data;
    free(l->first);
    l->first = NULL;
    l->length = 0;
    return data;
  } else {
    void *data = l->first->data;
    NODE *tmp = l->first->next;
    free(l->first);
    l->first = tmp;
    l->length--;
    return data;
  }

}

/* Return the position of an element in the list, or -1 if it does not exist */
int find(LIST *l, void* data)
{
  int i = 0;
  NODE *current = l->first;
  while (current != NULL) {
    if (current->data == data)
      return i;
    current = current->next;
    i++;
  }
  return -1;
}

/* Clean up list. TODO: Test this (since it's not used in lab) */
void destroy_list(LIST *l)
{
  NODE *current = l->first;
  NODE *next;
  while (current != NULL) {
    next = current->next;
    free(current->data);
    free(current);
    current = next;
  }
  free(l);
}

/* Return pointer to an integer with value n */
int* intpointer(int n)
{
  int* num = malloc(sizeof(int));
  *num = n;
  return num;
}

/* Test and demo subroutine */
int main()
{
  LIST *l = new_list();
  
  /* Should be zero */
  printf("Length: %d\n", l->length);

  /* Add some stuff to the list */
  int i;
  int *n;
  int *thing;
  for (i = 0; i < 10; i++) {
    n = intpointer(i);
    if (i == 4)
      thing = n; /* Keep this for searching, later */
    append(l, n);
  }

  /* Test find() */
  printf("Pos %d: %d\n", *(int*)thing, find(l, thing));
  int *other_thing = intpointer(12);
  printf("Pos %d: %d\n", *other_thing, find(l, other_thing));

  /* Test iteration */
  NODE* iter = l->first;
  printf("List: ");
  while(iter != NULL) {
    printf("%d ", *(int*)iter->data);
    /* Note: if reappending while iterating we might end up with an infinite
       loop. Try keeping a reference to the first reappended item if you want
       to break, or create a copy of the list */
    iter = iter->next; 
  }
  printf("\n");
  printf("Length: %d\n", l->length);

  /* Test pop() */
  int *popped = (int*)pop(l);
  while (popped != NULL) {
    printf("Pop result: %d\n", *popped);
    printf("Length: %d\n", l->length);
    popped = (int*)pop(l);
  }

  printf("Length: %d\n", l->length);

  /* Free up some memory */
  destroy_list(l);
  return 0;
}
/ Comment / programmering / c / chalmers / os

Reversing Wordpress Audioplayer url obfuscation

One of my favourite artists recently posted a new song to his blog. I wanted to download the mp3 file but he uses the Wordpress Audioplayer plugin, which obfuscates the original url of the file being played. The plugin is released under the open source MIT license so I had a look at the source code for decoding these urls. It turns out that the algorithm is really simple. Just look up each character in the obfuscated string in a key. Make a string of the position of each character’s position, represented as a six bit binary number, then just treat this string as a binary representation of an ordinary ascii string. My python version of the algorithm looks like this (download it): 

def int2bin(n):
    assert n >= 0, "Number must be positive"
    res = ""
    if n == 0: return "0"
    while True:
        if n == 0:
            return res
        elif n % 2 == 0:
            res = "0" + res
        else:
            res = "1" + res
            n -= 1
        n /= 2

def decode(source):
    key = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-"
    binary = ""

    for char in source:
        code = key.find(char) # look up each char in the code key
        binary += int2bin(code).rjust(6, "0") # append char index as a six bit binary string
    
    chunks = [] 
    # split string into segments of length 8
    while len(binary) > 0:
        chunks.append(binary[:8]) 
        binary = binary[8:]

    chars = [chr(int(x, 2)) for x in chunks] # convert the segments to chars
    return "".join(chars)

# http://www.mabd.se/?p=682
test = "aHR0cDovL3d3dy5tYWJkLnNlL3VwbG9hZC8yMDEwLzEyL0RlbWVudG9yZXIubXAzA"
print(test, decode(test))
/ Comment / python / programmering

Emacs, Facebook and lisp

I’m still learning new stuff in Emacs every day. It’s probably one of the main reason why Emacs is my favourite text editor; it’s just plain fun.

I happen to know a little Lisp, which come in handy sometime. Changing or extending the behavíour of a program is seldom easy, fun or even productive. Emacs is of course an exception. Once you know the basics you can do pretty much whatever comes to mind.

Today I made my first attempt at building an “interactive” function. A function that you can run by entering M-x function-name, that is. It’s called facebook-log-fix and I needed it because I really like saving my online conversations. Pidgin does this for me most of the time but when I chat on Facebook I need to save them myself. The problem is that Facebook’s stylesheets takes care of the layout of the chat, so when you simply copy the conversation to a text editor it gets all jumbled up. This simple little function takes care of this for me. Maybe you’ll like it, or just learn something about how to modify Emacs a little. Please tell me if you have got any suggestions for improvements — I’m a pretty big noob when it comes to lisp and Emacs.

Here it goes, just paste it into your .emacs file or whatever.

(defun facebook-log-fix nil
  "Make proper adjustments to a cut'n'pasted Facebook chat"
  (interactive) ; make the function available to the user
  (message "Trying to cleanup Facebook chat")
  (save-excursion ; restore stuff (point, mark and current buffer) when done
    ; Fancy regexp: (name)\n((anything+\n)*?[non-greedy])(time of day)
    (replace-regexp "\\(.*?\\)\n\\(\\(?:.*\n\\)*?\\)\\([0-9][0-9]:[0-9][0-9][a|p]m\\)"
                    "\\3 \\1 \\2\n"
                    nil 0 (buffer-size))))
/ Comment / programmering / lisp / emacs / facebook

Gource

Det här är en video från ett litet projekt jag jobbat på de senaste veckorna. Projektet heter “Fältrevision virkestillredning”, inte speciellt spännande namn kanske. Videon är däremot rätt cool tycker jag. Den är genererad med gource, ett litet program som kan skapa den här typen av animerade grafer från git-loggar (det kan även använda svn eller http-loggar mm.)

Tack för tipset Alex.

Den lilla gubben som flyger omkring symboliserar mig, bollarna är filer och när gubben skjuter på bollarna med laser (eller vad det ska föreställa) så är det jag som ändrar en fil. Hrm.

Det är väldigt enkelt att använda gource, även att generera videofiler (annars visas animationen bara på skärmen). Jag gjorde så här:

$ gource /sökväg/till/gitförrådet -s 3 \
    --disable-progress --output-ppm-stream /sökväg/till/utdatafil.ppm
$ ffmpeg -y -b  3000K -r 60 -f image2pipe -vcodec ppm \
    -i /sökväg/till/utdatafil.ppm -vcodec libx264 \
    -vpre default /sökväg/till/video.mp4
/ Comment / git / php / programmering / gource

PHP implementation of the MySQL old_password function

MySQL has a built in function called password that calculates the hash of a password for secure storage in a database. In MySQL versions older than 4.1 the hashing function was very basic so all newer versions uses the cryptograpichally secure SHA-1 hashing algorithm (twice?).

It comes as no surprise that many older databases are full of hashes calculated using the older algorithm. Fortunately it is still available under the name old_password. I needed the hashes from the old_password function but I didn’t want to connect to a database server each time. I looked up the old_password (it’s actually called my_make_scrambled_password_323 internally) from the MySQL source code. It’s written in C so a rewrite in PHP was pretty trivial. PHP doesn’t have the unsigned integer concept so I had to do some adding in the end to make the results come out right. It hasn’t been tested much and it probably only works for plain ASCII so use it at your own risk. Here it goes. 

function old_password($password) {
  if ($password == '')
    return '';
  $nr = 1345345333;
  $add = 7;
  $nr2 = 0x12345671;
  foreach(str_split($password) as $c) {
    if ($c == ' ' or $c == "\t")
      continue;
    $tmp = ord($c);
    $nr ^= ((($nr & 63) + $add) * $tmp) + ($nr << 8);
    $nr2 += ($nr2 << 8) ^ $nr;
    $add += $tmp;
  }

  if ($nr2 > PHP_INT_MAX)
    $nr2 += PHP_INT_MAX + 1;

  return sprintf("%x%x", $nr, $nr2);
}
/ Comment / programmering / php / mysql

Principerna bakom Erlang

Robert Virding, en av de ursprungliga utvecklarna bakom programmeringsspråket Erlang har just släppt ett intressant dokument där han beskriver hur de tänkte när de skapade språket. Vilka krav de hade, vilka designbeslut som togs och varför vissa saker ser ut som de gör. Han beskriver också ganska utförligt hur språket kunde sett ut om de hade valt andra vägar, och varför det inte hade varit lika bra. Immutable (oföränderliga) data till exempel.

Immutable data suits a high-level language, having mutable data gets you in to all sorts of trouble and difficulties, just read descriptions of other languages which have it and the difficulties in describing what gets changed and when, for example Python’s copy and deep_copy. Mutable data, however, is much easier to comprehend in a low-level language like C, K&R C, where you directly see which data is passed by value and which is passed by reference, i.e. mutable.”

Ett annat intressant parti är när han förklarar hur deras pragmatiska inställning till programspråksdesign har gett upphov till makron och records - fula programkonstruktioner kan gå an om de ger stora fördelar.

/ Comment / programmering

How to use UTF-8 with MySQL and PHP Data Objects (PDO)

If you are using PHP Data Objects (PDO) and are having trouble getting UTF-8 out of your MySQL server, even though everything is set to UTF-8 explicitly, you might want to try this:

$pdo = new PDO(
    'mysql:host=mysql.example.com;dbname=example_db',
    "username",
    "password",
    array(PDO::MYSQL_ATTR_INIT_COMMAND => "SET NAMES utf8"));

The last parameter of the PDO constructor call is the driver specific options, given as an array with key => value pairs. The MySQL driver have a “PDO::MYSQL_ATTR_INIT_COMMAND” option where you can specify a command that is executed every time you connect to the database. The MySQL specific query “SET NAMES utf8” is simply telling MySQL to use UTF-8 as the character set for our connection.

Read more:

/ Comment / programmering / php / sql / mysql