CSEDU Training 2012 Week 1

Today, we discussed several data structure dependent problems from this page. Most of them are classical type, i.e. common problems and we found the solution ideas quite interesting.

Here is the summery:

#0: Lazy propagation and slicing (compressing search space) ideas in segment tree.

#1: Finding number of intersecting points among axis parallel line segments.

#2: Perimeter and area of union of rectangles.

#3: Finding points in number of rectangles and rectangles covering points.

#4: Sliding window ideas, finding maximal number of points covered by a rectangle placed arbitrarily.

-- and a few others.

After the discussion, we solved this problem to test if we were able to learn anything at all.

Hopefully, the next class, we will have a discussion on the problems on APIO:2007

Problems to be solved before the next class:

SUBSEQ
GSS1
GSS3
GSS5
INCSEQ
INCDSEQ
LIS2
LPERMUT
FREQUENT

All are from http://www.spoj.pl/

Edit: A virtual contest has been arranged. Visit this link.

Running Java Program Without Console

How to run a java executable or jar without popping up the command prompt window?

This can be done by running the following command instead of "java", assuming the jar file is named "Main.jar"

javaw -jar -Xms1024m -Xmx1024m Main.jar

For example, lets start with the following simple snippet, it just creates a frame and we will the run the program without the black console window. Lets name the file as FacelessVoid.java

import javax.swing.*;

public class FacelessVoid {
    public static void main(String[] args) throws Exception {
        JFrame frame = new JFrame("FrameDemo");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(300, 300);
        frame.setVisible(true);
    }
}

Running the program from IDE's will straight show you the window, which contains nothing at all. This is just for demonstration purpose, so fill free to try something else if you need. Now, we will create a jar file containing this class (we are in windows os).

javac FacelessVoid.java
echo Main-Class: FacelessVoid > manifest.txt
jar cfm Main.jar manifest.txt FacelessVoid.class

Note, if you have more than one source file, i.e. .java files, you can write *.java instead of where we put FacelessVoid.java in line 1. In line 2, the main class name should be the class which contains the main() method. In line 3, if there are more than one class file to be put into jar file, you can use *.class instead of just FacelessVoid.class in our example.

If everything goes fine, the jar file named Main.jar should be created without any problem. Now we can create a batch file in the same directory where the Main.jar is located, lets call it Main.bat, we just put the following line into it:

start javaw -jar -Xms1024m -Xmx1024m Main.jar

Now double clicking on Main.bat will open the window without any command prompt window.

How can I vanish the window totally but still keep the program running?

There are a few ways to do this, I am presenting here a simple way using the previous files, the only thing needed to change is frame.setVisible(true); to frame.setVisible(false); This will hide the window now completely but the program is still running. Note, you will need to create the jar file again, i.e. re-compile and the make jar again. Now if you click on the bat file, it will start executing, but you wont be able to see it any more.

This can be helpful for servers which remains idle and waits for clients. We can just put them beyond visibility and they still keeps executing. For example, this code is just a modification of the previous one, and it will wait for a client to connect on the specified port. However, whenever a client gets a connection, we just change the visibility just to show that the program was actually running even though we were not able to see it. So you may wish to remove the line frame.setVisible(true); from the while loop and write your own program logic and make it permanently invisible.

import javax.swing.*;
import java.net.*;

public class FacelessVoid {
    public static void main(String[] args) throws Exception {
        JFrame frame = new JFrame("FrameDemo");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(300, 300);
        frame.setVisible(false);
        ServerSocket ss = new ServerSocket(8080);
        Socket client = null;
        while((client = ss.accept()) != null) {
            frame.setVisible(true);
        }
    }
}

Now, we can keep the server running without being able to see it. Here is a sample client program at your disposal

import java.net.*;

public class Client {
    public static void main(String[] args) throws Exception {
        Socket sock = new Socket("localhost", 8080);
    }
}

You just run and compile it and the server window will pop in from nowhere :D

Let me know if this works for you too...

Character Device Driver

Linux Kernel Programming: Writing a simple character device driver

Probably the simplest example for a simple linux device driver is a character device driver using virtual buffer, i.e. without using any real device, a block of memory will be used to simulate the properties of a buffer. We will be dealing only with the major device number, minor device number is used internally by the driver, but will be skipped in this example for simplicity. Also, the major number will be statically declared. I call this device "chardev", however, you can put any name you like. Like any other kernel driver modules, it has 6 basic functionalities, among which, two are module_init and module_exit functions, namely, device_init and device_exit. The rest four functions are from file_operations structures, read, write, open and release which are accomplished by device_read, device_write, device_open and device_release functions here. Actions of each functions are quite simple, device_init registers the device when the module is loaded and device_exit unregisters it upon removal. device_open tracks whether the device is already open or not, and device_release may be used to free any used space, however, we are allocating memory statically, so nothing much to do here. And finally, device_write is used to write a string to the device buffer which is in kernel space from an address which is in user space, for example, when we use `echo "hi" > /dev/chardev`, string "hi" (without quotes) will be written to device buffer. device_read is the opposite of device_write function. It is used when user space calls the device to read something from the buffer, for example `cat /dev/chardev`. Basically what it does is, just exports buffer data to a user space address. More details of each operation and functions used here in the text books or from online resources. Now here is a simple implementation. Don't expect it to be too smart anyway.

/*
AUTHOR: Zobayer Hasan
PROGRAM: Character Device Driver
DATE: Monday, 25 July 2011
VERSION: 1.0
*/

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/moduleparam.h>
#include <linux/init.h>
#include <linux/slab.h>
#include <linux/fs.h>
#include <linux/fcntl.h>
#include <linux/stat.h>
#include <linux/types.h>
#include <linux/errno.h>
#include <asm/system.h>
#include <asm/uaccess.h>

#define DEVICE_NAME "chardev"
#define BUFFER_SIZE 1024

MODULE_LICENSE("Dual BSD/GPL");
MODULE_AUTHOR("Zobayer Hasan");
MODULE_DESCRIPTION("A simple character device driver.");
MODULE_SUPPORTED_DEVICE(DEVICE_NAME);

int device_init(void);
void device_exit(void);
static int device_open(struct inode *, struct file *);
static int device_release(struct inode *, struct file *);
static ssize_t device_read(struct file *, char *, size_t, loff_t *);
static ssize_t device_write(struct file *, const char *, size_t, loff_t *);

module_init(device_init);
module_exit(device_exit);

static struct file_operations fops = {
    .read = device_read,
    .write = device_write,
    .open = device_open,
    .release = device_release
};

static int device_major = 60;
static int device_opend = 0;
static char device_buffer[BUFFER_SIZE];
static char *buff_rptr;
static char *buff_wptr;

module_param(device_major, int, S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP);
MODULE_PARM_DESC(device_major, DEVICE_NAME " major number");

int device_init() {
    int ret;
    ret = register_chrdev(device_major, DEVICE_NAME, &fops);
    if(ret < 0) {
        printk(KERN_ALERT "chardev: cannot obtain major number %d.\n", device_major);
        return ret;
    }
    memset(device_buffer, 0, BUFFER_SIZE);
    printk(KERN_INFO "chardev: chrdev loaded.\n");
    return 0;
}

void device_exit() {
    unregister_chrdev(device_major, DEVICE_NAME);
    printk(KERN_INFO "chardev: chrdev unloaded.\n");
}

static int device_open(struct inode *nd, struct file *fp) {
    if(device_opend) return -EBUSY;
    device_opend++;
    buff_rptr = buff_wptr = device_buffer;
    try_module_get(THIS_MODULE);
    return 0;
}

static int device_release(struct inode *nd, struct file *fp) {
    if(device_opend) device_opend--;
    module_put(THIS_MODULE);
    return 0;
}

static ssize_t device_read(struct file *fp, char *buff, size_t length, loff_t *offset) {
    int bytes_read = strlen(buff_rptr);
    if(bytes_read > length) bytes_read = length;
    copy_to_user(buff, buff_rptr, bytes_read);
    buff_rptr += bytes_read;
    return bytes_read;
}

static ssize_t device_write(struct file *fp, const char *buff, size_t length, loff_t *offset) {
    int bytes_written = BUFFER_SIZE - (buff_wptr - device_buffer);
    if(bytes_written > length) bytes_written = length;
    copy_from_user(buff_wptr, buff, bytes_written);
    buff_wptr += bytes_written;
    return bytes_written;
}

/*
End of Source Code
*/

Ha, quite tiny code. obviously huge optimization and improvement await here. Now, we have assigned major number 60, before doing anything, make sure your system has not assigned 60 as a major number for any device. To check this, just use the command:

$ ls -l /dev

Just try to find out a number which is not already used as a major number (1st number) and assign it to the variable device_major, or you can do it through command line also when using insmod command to insert the module. To compile this program, just use the following Makefile (name the file Makefile):

obj-m := chardev.o
all:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) modules
clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(shell pwd) clean

Note, do not copy this, you must write it by typing to avoid problems, and spaces before keyword make must be tab character. And I assumed the source file name 'chardev.c'. I am using ubuntu platform, so you might need to change this a bit, however I think it will work just fine. To run the makefile, go to the directory it is in along with the sourcefile,

$ sudo make

If you don't get any errors, that means you have successfully compiled the source file to generate chardev.ko which is the kernel module. Now, you need to create a device with major number 60 or what you want to assign:

$ sudo mknod /dev/chardev c 60 0
$ sudo chmod 666 /dev/chardev
$ sudo insmod chardev.ko

In mknod command, c defines that it will be a character device, then we give read+write permissions for everyone, so that the device can be usable. Then insmod command inserts chardev device in modules, you can see it in various ways, like, using `lsmod | grep chardev` or `ls -l /dev | grep chardev` or `modinfo chardev` or you can just use `dmesg` to display kernel log to see whether the loading printk printed anything (last line of the output of dmesg command). Now it's upto you to do some experiments, like to write to device, just redirect the output of any program with a output redirect operator `>` (be careful, buffer here is allocated only 1KB). And to read from the device, open it (/dev/chardev) with any program and read from it, like, just using `cat /dev/chardev`. Finally, when done with experimenting, you may wish to unload the driver and remove the device:

$ sudo rmmod chardev
$ sudo rm /dev/chardev

That's pretty much of it. Good luck & have fun!