By the way, the asymmetry in the following is not due to anything inherent in networking or the different Linux kernels. Rather, the 486 will one day be my portal to the Internet. It shouldn't be able to do much of anything other than responding to someone it knows. On the other hand the other two should have no restrictions.

Other than that, be careful: this is merely intended to get up and running as quickly as possible. Everything else has been pretty much ignored. Consider this just a small but important first step. Your next step has to be the relevant documentation because this is quite superficial!

1. Quick-Start - Ethernet

Other than a PCMCIA problem (see below), installing and configuring Ethernet is rather straight-forward. To keep things simple I started out with a cross-over cable, i.e. point-to-point, and moved on to a switch only after everything else was known to work.

Rather than having each machine connect to the network at boot, there are scripts in /root to run when it is time to connect. Here are the relevant scripts and files from two of the machines (less comments and stuff not relevant here):

Toshiba 486

     /etc/hosts:       127.0.0.1      localhost
                       192.168.0.99   Toshiba486.Lohgo  Lohgo486
                       192.168.0.100  ToshibaAMD.Lohgo  LohgoAMD
                       192.168.0.101  PC.Lohgo          LohgoPC

     /etc/hosts.allow: sshd: 192.168.0.100, 192.168.0.101

     /root/eth-up:     #!/bin/bash
                       /sbin/ifconfig eth0 192.168.0.99 \
                                      broadcast 192.168.0.255 \
                                      netmask 255.255.255.0 up

Pentium 166

     /etc/hosts:       127.0.0.1      localhost         PC
                       192.168.0.99   Toshiba486.Lohgo  Lohgo486
                       192.168.0.100  ToshibaAMD.Lohgo  LohgoAMD
                       192.168.0.101  PC.Lohgo          LohgoPC

     /etc/hosts.allow: sshd:      192.168.0.100
                       portmap:   192.168.0.100
                       lockd:     192.168.0.100
                       rquotad:   192.168.0.100
                       mountd:    192.168.0.100
                       statd:     192.168.0.100

     /root/eth-up:     #!/bin/bash
                       /sbin/insmod rtl8139
                       /sbin/ifconfig eth0 192.168.0.101 \
                                      broadcast 192.168.0.255 \
                                      netmask 255.255.255.0 up

The following are the same on all 3 machines:

     /etc/hosts.deny:  ALL : ALL

     /root/eth-down:   #!/bin/bash
                       /sbin/ifconfig eth0 down

     /root/eth-stat:   #!/bin/bash
                       /sbin/ifconfig eth0; /bin/netstat -r

The extra entries for the P166 in /etc/hosts.allow are to support nfs. And insmod in /root/eth-up is due to the Ethernet card in the PC vs PCMCIA on the notebooks.

Be aware that SuSE at installation has an option to "re-organize" /etc/hosts that defaults to CHECK_ETC_HOSTS=yes in /etc/rc.config. My suspicion is that this is what can cause the 192-IP-address to be replaced by a 127-address for the host itself in /etc/hosts on reboot. I don't reboot often enough to feel like checking this out. But if you get an inexplicable inability to access the network, do verify the contents of this file.

2. Quick-Start - Ssh

Without a doubt this is the most complex of the Linux facilities described here but is the key to a couple of things that are extremely useful and it certainly should be set up, for both convenience and security.

Prerequisites/definitions:

This is what you have to do if you don't bother to set ssh up:

Remote        Local          Comment

              <logon as user also known to remote host>
              ssh <host>
                             warning:... SOMETHING NASTY
              yes            accept it
              <password>

This is setup:

Remote        Local          Comment

              <l;ogon as user also known to remote host>
              /usr/bin/ssh-keygen
                             accept default: .ssh/identity
                             no passphrase
              mount /floppy
              cp .ssh/identity.pub /floppy/
              umount /floppy

logon as <the same user>
mkdir .ssh                   if necessary
mount /floppy
cp /floppy/identity.pub .ssh/authorized_keys
cp /etc/ssh/ssh_host_key.pub /floppy/known_hosts
umount /floppy

              mount /floppy
              cp /floppy/known_hosts .ssh/
              umount /floppy
              vi .ssh/known_hosts
                             add <host> at start of line and
                             remove root@<host> at end

And this is what you have to do to logon after setting things up:

Remote        Local          Comment

              <logon as user also known to remote host>
              ssh <host>

Note that the host key is generated as part of system installation (with SuSE anyhow). And there can be differences in directory structure (SuSE's kernel 2.2 didn't have 'ssh' under 'etc'). Also note that this is just intended to get someone unfamiliar with ssh up and running. Do not blindly follow these steps if you have used ssh before! In particular most 'cp's certainly ought to be 'cat ... >>'. In the office at home I don't want a passphrase to begin work on a different machine, but you might.

3. Quick-Start - Screen

Although it has been mentioned in Linux Gazette several times and I actually did play with it briefly, the need for screen wasn't at all obvious to me. Given 6+ vt's and X running on at least two others with unlimited windows under whatever window manager one has running, it seemed just another level of complexity.

The need became obvious as the network at home began taking shape. The rationale behind screen boils down to this: if you start sessions on remote machines under screen, they remain available to you as long as the remote machine isn't shut down -- independent of what happens on the communication link or your local machine. Like one of my PCMCIA Ethernet cards only works under Windows and I can thus only connect one of the notebooks to the PC at a time, if the AMD is also running Linux, as it usually is -- but no need to shut the 486 down, just eject the card, pop it into the AMD and screen keeps sessions active on the 486 for later access.

To start screen:

    screen -R   restart session if available, otherwise start one

Within screen (not at all apparent, it hides well) use Ctrl-a followed by:

    ?   help
    w   show list of windows
    n   switch to next window
    c   create new window
    d   disconnect
    A   assign title to window

4. Quick-Start - File Transfer

If you are using ssh, you can get rid of rsh -- and telnet and ftp as well for that matter. Here are a couple of alternatives that to me are more convenient than the lot.

Netcat is a nifty little tool, analogous to cat. You start it to receive a file on one machine

    netcat -vv -l -p <port> > <file>

and then tell the other machine what to send

    netcat -vv -w 10 <hpopst> <port> < <file>
or
    tar -czvf - <directory> | netcat -vv -w 10 <host> <port>

Use netstat and /etc/services to find an available port. The option "-w 10" tells the sender to terminate the connection after 10 seconds of inactivity and the option "-vv" lets you verify that the correct number of bytes was sent and received.

While netcat holds promise for scripts to backup to a different machine as the network at home gradually takes shape, Midnight Commander has amazing facilities for the things one simply has to do by hand.

If ssh has been set up properly, the following entered in the command line makes mc's active panel point to the same user on the "other" machine -- yes, "#sh" not "#ssh", unfortunately

    cd /#sh:<host>

And if the other side has anonymous ftp running, the following should be fairly self-explanatory

    cd /#ftp:www.tldp.org/

5. Quick-Start - NFS

I played around with nfs and it works but unfortunately my notes are non-existant (basically just check-marks in the printout of the HOWTO). As I recall, besides installing the relevant package on client and server all that was needed was to edit /etc/exports on the PC (server) as follows:

/home	192.168.0.100(rw,root_squash,sync,insecure)
/tmp	192.168.0.100(rw,root_squash,sync,insecure)

At installation SuSE has a number of options to be selected, many (all?) of which wind up in /etc/rc.config. Here is an excerpt of those relevant to nfs:

START_PORTMAP="yes"
NFS_SERVER="yes"
USE_KERNEL_NFSD="yes"
USE_KERNEL_NFSD_NUMBER="4"
NFS_SERVER_UGID="no"
REEXPORT_NFS="no"

On the AMD (client) I added the following to /etc/fstab:

192.168.0.101:/home	/Rhome	nfs	noauto,users,sync 0 0
192.168.0.101:/tmp	/Rtmp	nfs	noauto,users,sync 0 0

At that point the mount command works with /Rhome etc. just as well as /floppy or any other entry in fstab. One minor annoyance is that user ID's must be the same on all machines using nfs. This was not a problem for me because, when installing Linux, I create the few users in the same order.

6. Quick-Start - Samba

Given the difficulty of keeping track of what one is doing under Windows, particularly with false starts and things that turn out to be wrong or simply irrelevant, this needs to be taken with a large grain of salt. It assumes that the driver for the PCMCIA card has been installed, if relevant. And if the terminology is slightly obscure, that is due to my translating from the German versions of Windows.

The following is what was necessary to enable logon to the PC from the AMD under Samba, i.e. from Windows 98 to Linux 2.2.13 (SuSE 6.3). With appropriate adjustments the same steps worked in the other direction, i.e. from Windows 95 to Linux 2.4.18-4GB (SuSE 8.0). But note these differences:

Part 1 - Linux
                             edit /etc/smb.conf
[global]
   workgroup = Lohgo
   encrypt passwords = yes
   smb passwd file = /etc/smbpasswd
   password level = 8
   username level = 8
   socket options = TCP_NODELAY
   domain logons = yes
   domain master = yes
   os level = 65
   preferred master = yes
   wins proxy = no
   wins support = yes
   hosts allow = 192.168.0.100 127.
[homes]
   comment = Home Directories
   read only = no
   browseable = no
[netlogon]
   comment = Network Logon Service
   path = /usr/local/samba/netlogon
   public = no
   writeable = no
   browseable = no
[profiles]
   path = /home/%U/profile
   guest ok = yes
   browseable = no
                             confirm validity, should show no errors
testparm | less
                             create user w/password
smbpasswd -a web
                             verify user enabled
smbpasswd -e web
                             start Samba
smbd -D
nmbd -D
                             at this point from the client -- under
                             Linux, not Windows -- the following
                             should give a meaningful response
smbclient -L LohgoPC
                             and the following should give you
                             ftp-like access
smbclient //LohgoPC/web

Part 2 - Windows98

control panel | network | configuration
  add | client for microsoft network
  properties
    Windows NT-domain: Lohgo
    quick logon
  add | protocol | microsoft | tcp/ip
  properties | set IP-address
    IP-address:     192.168.000.100
    Subnet address: 255.255.255.000
  primary network logon: client for Microsoft network
control panel | network | identification
  computer name: LohgoAMD
  workgroup:     Lohgo
  description:   ToshibaAMD.Lohgo
control panel | passwords | user profiles
  users can customize: both
reboot
                             if using PCMCIA the following puts
                             a symbol on the task bar with which
                             the PCMCIA card can be removed
<insert PCMCIA Ethernet card and wait for lights to settle down>
                             the following works ONLY after TCP/IP
                             has been set up, shows configuration
start | run | winipcfg
                             test connection from within a dos-box
ping -n 5 192.100.0.101
                             edit c:\windows\hosts.sam
127.0.0.1       localhost
192.168.0.101   lohgopc
                             edit c:\windows\lmhosts.sam
192.168.0.101   lohgopc

At this point after booting, Windows will ask you to logon, which you can either do with a user known to Samba or cancel to use Windows without the network as before. Now, however, the pop-up window opened by Ctrl-Esc includes near the bottom a line to logoff that afterwards provides the same logon prompt as booting. And the entries in the task bar -- in the home directory, anyhow -- tell you who and where you are, as in

"Explorer - <user> at <host>"

where "<host>" is the 3rd column of the entry for the Linux machine in /etc/hosts on the Linux machine.

Symbolic links work quite nicely. The following executed within the home directory of some user makes a directory -- even on a different partition -- on the Linux machine available to that user on the Windows machine:

ln -s /dos/f/pictures pictures

Due to a shortage of resources on the PC and the fact that I have no real use for Windows anyhow, I use the following scripts to start and stop the Samba daemons on the PC as needed:

/root/samba-up:     #!/bin/bash
                    /usr/sbin/smbd    -d3    -l /tmp/sbd.log
                    /usr/sbin/nmbd -D -d0 -o -l /tmp/sbd.log

/root/samba-down:   #!/bin/bash
                    kill -s SIGTERM $(ps aux | grep mbd \
                        | grep -v grep | awk '{print $2}')

[printers]
   comment = All Printers
   browseable = no
   printable = yes
   public = no
   read only = yes
   create mode = 0700
   directory = /tmp

control panel | printer | new printer
  network printer | search
    network environment | Pc
      hpdj-a4-raw
    manufacturer: HP
    printer:      HP OfficeJet

7. Quick-Start - PCMCIA

To be honest I have no idea whether this is generally applicable or is specific to SuSE (8.0). And it was only the 2.4 kernel that had problems with PCMCIA, not 2.2 strangely enough. Also, it has nothing to do with networking per se. But if you're going to connect a notebook to your network, you'll probably have to confront the alphabet monster. And a PCMCIA Ethernet card makes a delightful docking station.

Omitting many details, I initially failed to note an inconsistency with references to irq 5 and 10 that later led to tons of error messages. But this was due to having inserted the PCMCIA card before starting the installation of Linux.

In my case at least, by not inserting the PCMCIA card before starting installation, there was a reference to only one irq which led to my doing the following.

After initial boot in /etc/sysconfig/pcmcia add

	PCMCIA_PCIC="i82365"
	PCMCIA_PCIC_OPTS="irq_list=10"

However, installing the PCMCIA software before doing this causes the notebook to hang irrevocably on boot. The only way to boot is by giving LILO the parameter NOPCMCIA=yes. Instead, I installed the PCMCIA software after SuSEconfig and before reboot.

After that, inserting the PCMCIA card produces a couple of beeps and it works as advertised. Since this is my first personal experience with Ethernet, I can't comment on alternatives but the D-Link DFE-650TXD PCMCIA Ethernet card works well, Linux-to-Linux anyhow (a couple of hours sending stuff over the network before risking the wretched "Recovery CD-Rom" to make Windows 98 work again) and has lots of LEDs to let you know what is going on.

Here is the output from /sbin/cardctl config and ident.

CONFIG:

Socket 0:
  not configured
Socket 1:
  Vcc 5.0V  Vpp1 0.0V  Vpp2 0.0V
  interface type is "memory and I/O"
  irq 10 [exclusive] [level]
  function 0:
    config base 0x0400
      option 0x60 status 0x00 copy 0x00
    io 0x0300-0x031f [auto]

IDENT:

Socket 0:
  no product info available
Socket 1:
  product info: "D-Link", "DFE-650TXD", "Fast Ethernet", "Rev. A1"
  manfid: 0x0149, 0x0230
  function: 6 (network)

8. Further Reading

See also the following articles in the issue of Linux Gazette indicated:
36: Introducing Samba by John Blair
39: Expanding Your Home Network by J.C. Pollman
44: DNS for the Home Network by J.C. Pollman and Bill Mote
47: Backup for the Home Network by J.C. Pollman and Bill Mote
48: SAMBA, Win95, NT and HP Jetdirect by Eugene Blanchard
50: Sharing your Home by J.C. Pollman and Bill Mote
57: Making a Simple Linux Network Including Windows 9x by Juraj Sipos
61: Using ssh by Matteo Dell'Omodarme
64: ssh suite: sftp, scp and ssh-agent by Matteo Dell'Omodarme
67: Using ssh-agent for SSH1 and OpenSSH by Jose Nazario
74: Play with the Lovely Netcat by zhaoway

The Linux Gazette Answer Gang Knowledge Base under Network Configuration has numerous relevant tidbits among which Routing and Subnetting 101 is mandatory reading.

And the Linux Focus Index by Subject under System Administration has several articles well worth looking at, e.g.:
Replacing a Windows/NT/2000 server using Linux and Samba by Sebastian Sasias
Through the Tunnel by Georges Tarbouriech
Samba Configuration by Eric Seigne
Network File System (NFS) by Frederic Raynal
Home Networking, glossary and overview by Guido Socher

9. A Future without Windows?

Coming from pre-TRS-80 days, I've used DOS, various versions of Windows, at least 3 releases of OS/2, Coherent, and now 5 releases of SuSE Linux over at least 5 years. I am convinced that anyone in a position to "compare and contrast" would agree that at best Windows is unstable junk. One of my goals for a quite some time had been to gain complete independence from Windows.

But consider: our ISDN phone system has an RS-232 connector with which it can be programmed via -- yeah, you got it. One of the printers is USB for the notebook and guess whose drivers are available. Our digital camera uses smart media and the USB smart media reader... Oh, well, you get the picture.

I've only had Samba working for a week and actually hadn't even intended to check it out but everything else worked so well that it seemed worth a try. And it's so slick that I question whether it would really be worth my effort to try to find replacement drivers for this legacy stuff. How many hours, how many experiments, what guarantee of success? Doesn't it make more sense to boot the notebook under the "silly system" (I hope Monty Python put that under GPL) and use the Samba connection to the rest of the network? At least until the last Windows-legacy device eats it.

Edgar is a consultant in the Cologne/Bonn area in Germany. His day job involves helping a customer with payroll, maintaining ancient IBM Assembler programs, some occasional COBOL, and otherwise using QMF, PL/1 and DB/2 under MVS.

...making Linux just a little more fun!

A Keep-Alive Program You Can Run Anywhere By Graham Jenkins

The Poodle and the Labrador

You are halfway through typing a new program into a remote machine connected over a dial-up line, and you get called to intervene in a fight between your partner's miniature poodle and the neighbour's ugly yellow Labrador. When you get back, your connection has timed-out.

Is this something that has happened to you? Or perhaps you had to drag your kids away from a particularly offensive episode of Jerry Springer, then found you had to stick around to make sure they didn't come back?

The Blonde Solution

The traditional procedure for maintaining activity on your line during an interruption of the type outlined above was to use a 'fortune' program in a small loop so that a random saying got written to your screen every half-minute. This could present some real problems if a person with fair hair looked at your screen and saw something like:

 Q:  How do you make a blonde's eyes light up?
 A:  Shine a flashlight in her ear.

You could of course used a '-i' or equivalent parameter restricting 'fortune' to generating inoffensive material like:

  Computing Definition
  Chaining - A method of attaching programmers to desk, to speed up output.

The more recent incarnations of the 'fortune' program offer their users a more specific set of options. You can chose between offending those who are Irish, gay or intellectually retarded!

For The Terminally-Challenged

If you are just using a browser to read your Hotmail messages, you probably won't want to open a terminal window just so you can run a 'fortune' program. If you are using an X11-compliant window-manager, you could start a clock program with something like:

 xclock -digital -update 1 &

But that's not going to work on your your vintage Windows 95 machine unless you also happen to be running something like PC-Xware.

The 'KeepAlive.java' program listed here is designed to work anywhere. It's written in Java 1.1 so that even the 'jview' virtual machine on your basic Microsoft machine can handle it. It doesn't rely on finding a 'fortune', 'xclock' or other program on a remote machine. And you don't have to change anything when you connect via a different ISP.

Finding A Partner

But you have to send traffic somewhere, right? So how do you find a partner machine which will receive your traffic? If we were writing this program as a shell script, we might work out where our gateway was, and ping it at appropriate intervals. That's not so easy to do in a Java program which might run on any number of platforms. And in any case, it would be nice if we could send traffic somewhere beyond the gateway machine.

In almost every sort of networking arrangement, the participating machines have knowledge of one or more nameserver addresses. So what we can do from our Java program is make periodic requests to those nameservers. We need to ensure that any hosts whose addresses we request cannot be found locally in a hosts table. And we need to also ensure that the answers to our nameserver requests are not cached locally. If you take a look now at the program, you will see that the names of the hosts whose addresses we are requesting are generated by examining the clock-time in milliseconds at the time of each request. This results in names like A1040689223909, A1040689229448, etc.

That's really all we need to do. But it's nice to be able to see something happening. So our program defines a 'MessageFrame' class which displays two colored buttons in a GUI window. The colors of these are changed at each iteration. We also set the title on the GUI window, and change it at each iteration - so we can still see something happening when the window is minimized. And we set up a listener to detect 'window closing' events and perform a graceful shutdown.

Getting It Together

Here's the program. You need to compile it with a command like:

 javac KeepAlive.java

 java KeepAlive

 java KeepAlive

/* @(#) KeepAlive.java  Trivial keep-alive program. Tries at 5-second intervals
 *                      to find addresses for hosts with generated names. This
 *                      ensures that messages are sent to nameserver(s).
 *                      Copyright (c) 2002 Graham Jenkins <grahjenk@au1.ibm.com>
 *                      All rights reserved. Version 1.06, August 15, 2002.
 */
import java.io.*;
import java.net.*;
import java.awt.*;
import java.awt.event.*;
import java.util.Date;
public class KeepAlive {
  public static void main(String[] args) {
    MessageFrame f=new MessageFrame();  // Change button colours each iteration.
    int flag=0;                         // Also switch frame-title so we can see
    while ( true ) {                    // activity whilst iconified.
      f.statusMess(Color.red,Color.red); f.setTitle("==X==");
      try {InetAddress addr=InetAddress.getByName("A"+(new Date()).getTime());}
      catch (UnknownHostException ioe) {}
      if(flag==0) {f.statusMess(Color.yellow,Color.green); f.setTitle("1.06");}
      else {f.statusMess(Color.green,Color.yellow); f.setTitle("KeepAlive");}
      flag=1-flag;
      try {Thread.sleep(5000L);} catch (InterruptedException e) {}
    }
  }
}

class MessageFrame extends Frame implements ActionListener {
  private Button b1, b2;                // Displays two coloured buttons.
  public MessageFrame() {
    Panel p=new Panel(); p.setLayout(new FlowLayout());
    b1=new Button() ; b2=new Button(); p.add(b1); p.add(b2);
    this.add("South",p); this.setSize(150,50); this.show();
    this.addWindowListener(new WindowAdapter() {
      public void windowClosing(WindowEvent e) { System.exit(0); }
    });
  }
  public void statusMess(Color left, Color right) {
    b1.setBackground(left); b2.setBackground(right);
  }
  public void actionPerformed(ActionEvent e) {}
}

If you have Java 1.1 or later, and no requirement to use the Microsoft virtual machine, you can assemble the class files into a single 'jar' file, then execute it using the '-jar' option thus:

  echo "Main-Class: KeepAlive\015" >/tmp/MyManifest
  jar cmf /tmp/MyManifest /tmp/KeepAlive.jar *.class
  
  java -jar /tmp/KeepAlive.jar

If You Don't Have It

If your machine doesn't have Java, you can get it from Sun MicroSystems. And if you need to know more about network programming with Java, you could take a look at "Java Network Programming and Distributed Computing" by David Reilly and Michael Reilly.

Graham is a Unix Specialist at IBM Global Services, Australia. He lives in Melbourne and has built and managed many flavors of proprietary and open systems on several hardware platforms.

...making Linux just a little more fun!

Linux-Based Voice Recognition By Janine M Lodato

Let's look at Linux-based voice recognition software from the perspective of China. It would behoove Linux computer makers anyway to begin manufacturing their computers in China, because China offers a low-cost method of manufacturing and provides them with a large market for their hardware which can also be exported to other important markets around the world.

Linux computers have the capacity to accommodate voice recognition systems, such as IBM ViaVoice. This is especially advantageous to Chinese speakers because both Mandarin and Cantonese are very complex in the written form, so documents could be more easily produced through voice recognition software running on a Linux platform. Using a keyboard is next to impossible for Chinese languages because so many characters are involved in typing a document.

Other languages will also benefit from using voice recognition software for purposes of speed. Hands-busy, eyes-busy professionals can benefit greatly from voice recognition so they don't have to use a mouse and keyboard to document their findings. Voice-activated, easily-used telephone systems will benefit all walks of life. Anyone driving a car will find voice recognition a much more effective way of manipulating a vehicle and communicating from the vehicle.

The health-care market alone may justify the Linux based voice recognition project. Health-care services are the largest expense of the Group of Ten nations, and it is the fastest growing sector as well. Health-care workers would benefit from using their voices to document describing the treatments of patients. Voice recognition allows them a hands-free environment in which to analyze, treat and write about particular cases easily and quickly.

Electronically connected medical devices via wireless LAN can benefit:

• ...Hospital administration staff
  • Improve the usage efficiency of resources
  • Achieve standardized, quality patient management
  • Dramatically reduce data recording (transcription) errors
  • Lower costs
  • Make any room a telemetry room on demand (that is, do laboratory measurements in any room regardless of where the central equipment is located)
• ...Medical staff
  • Be empowered with a 24/7 complete set of vital-sign data
  • Have more time for hands-on care
  • See changes in patient status immediately to enable quicker responses

In this life sciences field, the simplicity, reliability and low cost of Linux for servers, tablets, embedded devices and desktops is paramount. Only about 10% of the documents in the health-care field in the USA are produced electronically due to the cumbersome and unreliable nature of the Windows environment. 30% of the cost of health-care is a direct result of manual creation of the documents and many of the malpractice cases are also due to the imprecision of transcriptions of manually scribbled medical records and directives, as anybody who looks at a prescription can attest.

Obviously, the market for these new technologies exists. What remains is for a hungry company with aggressive sales people to tap into that market. Once those sales people get the technology distributed, the needs of many will be met and a new mass market will open up that Microsoft isn't filling: assistive technology (AT). Actually, the field already exists but needs to be expanded to include both physically disabled and functionally disabled.

Yes, voice recognition offers great promise for the future. However, it isn't perfect and needs to be improved. One improvement could use lip reading to bolster its accuracy. Still another is multi-tonal voice input. Another is directional microphones. Every generation of voice recognition software will improve as the hardware for Linux gets bigger and stronger.

...making Linux just a little more fun!

Perl One-Liner of the Month: The Adventure of the Arbitrary Archives By Ben Okopnik

Spring was in full bloom, and Woomert Foonly was enjoying another perfect day. It had featured a trivially easy configuration of a 1,000-node Linux cluster, and had been brought to an acme by lunching on Moroccan b'stila with just a touch of ras el hanout curry and a fruited couscous on the side, complemented by a dessert of sweet rice with cinnamon. All was at peace... until Frink Ooblick burst in, supporting - almost carrying - a man who seemed to be in the last extremity of shock. Frink helped him to the couch, then dropped into the easy chair, clearly exhausted by his effort.

 -- "Woomert, it's simply scandalous. This is Resolv Dot Conf, a humble... erm, well, a sysadmin, anyway. Recently, he was cruelly forced to install some kind of a legacy OS on his manager's computer - can you imagine? - and now, he's being asked to do something that sounds nearly impossible, although I could only get scant details. He had heard of your reputation (who hasn't, these days?), and was coming to see if you could help him, but collapsed in the street just outside your door due to the residual shock and a severe Jolt Cola deficiency. As to the problem... well, I'll let him tell you."

Woomert had been tending to their guest while listening, with the result that the latter now looked almost normal. Indeed, Woomert's "sysadmin-grade coffee" was well-known among the cognoscenti for its restorative powers, although the exact recipe (it was thought to have Espresso Alexander and coffee ice cream somewhere in its ancestry, but the various theories diverged widely after that point) remained a deep secret.

Now, though, the famous detective's eyes sharpened to that look of concentration he habitually wore while working.

 -- "Please state your problem clearly and concisely."

The quickly recovering sysadmin shook his head mournfully.

 -- "Well, Mr. Foonly... you see, what I have is a script that processes the data submitted to us by our satellite offices. The thing is, it all comes in various forms: we're a health insurance data processor, and every company's format is different. Not only that, but the way everyone submits the data is different: some just send us a plain data file, others use 'gzip', or 'compress', or 'bzip', or 'rar', or even 'tar' and 'compress' (or 'gzip'), and others - fortunately, all of those are just plain data - hand us a live data stream out of their proprietary applications. Our programmers handled the various format conversions as soon as they got the specs, but this arbitrary compression problem was left up to me, and it's got me up a tree!"

He stopped to take a deep breath and another gulp of Woomert's coffee, which seemed to revive him further, although he still sat hunched over, his forehead resting on his hand.

"Anyway, at this point, making it all work still requires human intervention; we've got two people doing nothing but sorting and decompressing the files, all day long. If it wasn't for that, the whole system could be completely automated... and of course, management keeps at me: 'Why isn't it fixed yet? Aren't you computer people supposed to...' and so on."

When he finally sat up and looked at Woomert, his jaw was firmly set. He was a man clearly resigned to his fate, no matter how horrible.

"Be honest with me, Mr. Foonly. Is there a possibility of a solution, or am I finished? I know The Mantra [1], of course, but I'd like to go on if possible; my users need me, and I know of The Dark Powers that slaver to descend upon their innocent souls without a sysadmin to protect them."

Woomert nodded, recognizing the weary old warrior's words as completely true; he, too, had encountered and battled The Dark Ones, creatures that would completely unhinge the minds of the users if they were freed for even a moment, and knew of the valiant SysAdmin's Guild (http://sage.org) which had sworn to protect the innocent (even though it was often protection from themselves, via the application of the mystic and holy LART [2]).

 -- "Resolv, I'm very happy to say that there is indeed a solution to the problem. I'm sure that you've done your research on the available tools, and have heard of 'atool', an archive manager by Oskar Liljeblad..."

At Resolv's nod, he went on.

"All right; then you also know that it will handle all of the above archive formats and more. Despite the fact that it's written in Perl, we're not going to use any of its code in your script - that would be a wasteful duplication of effort. Instead, we're simply going to use 'acat', one of 'atool's utilities, as an external filter - a conditional one. All we have to do is insert it right at the beginning of your script, like so:

#!/usr/bin/perl -w
# Created by Resolv Dot Conf on Pungenday, Chaos 43, 3166 YOLD

@ARGV = map { /\.(gz|tgz|zip|bz2|rar|Z)$/ ? "acat $_ '*' 2>/dev/null|" : $_ } @ARGV;

# Rest of script follows

...

The sysadmin was on his feet in a moment, fervently shaking Woomert's hand.

 -- "Mr. Foonly, I don't know how to thank you. You've saved... well, I won't speak of that, but I want you to know that you've always got a friend wherever I happen to be. Wait until they see this!... Uh, just to make sure I understand - what is it? How does it work?"

Woomert glanced over at Frink, who also seemed to be on the edge of his seat, eager for the explanation.

 -- "What do you think, Frink - can you handle this one? I've only used one function and one operator; the rest of it happened automagically, simply because of the way that Perl deals with files on the command line."

Frink turned a little pink, and chewed his thumb as he always did when he was nervous.

 -- "Well, Woomert... I know you told me to study the 'map' function, but it was pretty deep; I got lost early on, and then there was this new movie out..."

Woomert smiled and shook his head.

 -- "All right, then. 'map', as per the info from 'perldoc -f map', evaluates the specified expression or block of expressions for each element of a list - sort of like a 'for' loop, but much shorter and more convenient in many cases. I also used the ternary conditional operator ('?:') which works somewhat like an "if-then-else" construct:

# Ternary conditional op - sets $a to 5 if $b is true, to 10 otherwise
$a = $b ? 5 : 10;

# "if-then-else" construct - same action
if ( $b ){
        $a = 5;
}
else {
        $a = 10;
}

/\.(gz|tgz|zip|bz2|rar|Z)$/

This will match any filename that ends in a period (a literal dot) followed by any of the specified extensions.

Now, if the filename doesn't match the regex, the ternary operator returns the part after the colon, '$_' - which simply contains the original filename. Perl then processes the filename as it normally does the ones contained in @ARGV: it opens a filehandle to that file and makes its contents available within the script. In fact, there are a number of ways to access the data once that's done; read up on the diamond operator ('<>') , the STDIN filehandle, and the ARGV filehandle (note the similarity and the difference, Frink!) for information on some of the many available methods of doing file I/O in Perl."

"On the other hand, if the current element does match, the ternary operator will return the code before the colon, in this case

"acat $_ '*' 2>/dev/null|"

Perl will then execute the above command for the current filename. The syntax may seem a little odd, but it's what 'acat' (or, more to the point, the archive utilities that it uses) requires to process the files and ignore the error messages. Note that the command ends in '|', the pipe symbol; what happens here is much like doing a pipe within the shell. The command will be executed, the output will be placed in a memory buffer, and the contents of that buffer will become available on the filehandle that Perl would normally have opened for that file - presto, pure magic! [3]"

"So, to break it all out in long form, here's what I did:

@ARGV = 
        map {                                       # Use the BLOCK syntax of 'map'
                if ( /\.(gz|tgz|zip|bz2|rar|Z)$/ ){     # Look for archive extensions
                        "acat $_ '*' 2>/dev/null|"; # Uncompress/pipe out the contents
                }
                else {
                        $_;                         # Otherwise, return original name
                }
        } @ARGV;                                    # This is the list to "walk" over

 -- "Now, Resolv, I believe that you have a bright new future stretching out ahead of you; your problem will be solved, your management will be pleased, and your users will remain safe from Those Outside The Pale. If you would care to join us in a little celebration, I've just finished boiling a Spotted Dog, and - oh. Where did he go?... It's a very fine English pudding with currants, after all. Well, I suppose he wanted to implement that change as soon as possible..."

Footnotes

[1] "Down, Not Across." For those who need additional clues on the grim meaning of The Sysadmin Mantra, search the archives of alt.sysadmin.recovery at <http://groups.google.com>, and all will become clear. If it does not, then you weren't meant to know. :)

[2] From The Jargon File:

  Luser Attitude Readjustment Tool. ... The LART classic is a 2x4 or
  other large billet of wood usable as a club, to be applied upside the
  head of spammers and other people who cause sysadmins more grief than
  just naturally goes with the job. Perennial debates rage on
  alt.sysadmin.recovery over what constitutes the truly effective LART;
  knobkerries, semiautomatic weapons, flamethrowers, and tactical nukes
  all have their partisans. Compare {clue-by-four}.

[3] See "perldoc perlopentut" for a tutorial on opening files, the 'magic' in @ARGV, and even "Dispelling the Dweomer" for those who have seen too much magic already. :)

Ben is a Contributing Editor for Linux Gazette and a member of The Answer Gang.

Ben was born in Moscow, Russia in 1962. He became interested in electricity at age six--promptly demonstrating it by sticking a fork into a socket and starting a fire--and has been falling down technological mineshafts ever since. He has been working with computers since the Elder Days, when they had to be built by soldering parts onto printed circuit boards and programs had to fit into 4k of memory. He would gladly pay good money to any psychologist who can cure him of the resulting nightmares.

Ben's subsequent experiences include creating software in nearly a dozen languages, network and database maintenance during the approach of a hurricane, and writing articles for publications ranging from sailing magazines to technological journals. Having recently completed a seven-year Atlantic/Caribbean cruise under sail, he is currently docked in Baltimore, MD, where he works as a technical instructor for Sun Microsystems.

Ben has been working with Linux since 1997, and credits it with his complete loss of interest in waging nuclear warfare on parts of the Pacific Northwest.

...making Linux just a little more fun!

Fun with Simputer and Embedded Linux By Pramode C.E

Fun with Simputer and Embedded Linux

Hardware/Software

The device is powered by an Intel StrongArm (SA-1110) CPU. The flash memory size is either 32Mb or 16Mb and RAM is 64Mb or 32Mb. The peripheral features include:

1. USB master as well as slave ports.
2. Standard serial port.
3. Infra Red communication port.
4. Smart card reader

Some of these features are enabled by using a `docking cradle' provided with the base unit. Power can be provided either by rechargeable batteries or external AC mains.

Simputer is powered by GNU/Linux - kernel version 2.4.18 (with a few patches) works fine. The unit comes bundled with binaries for the X-Window system and a few simple utility programs. More details can be obtained from the project home page at www.simputer.org.

Powering up

There is nothing much to it, other than pressing the `power button'. You will see a small tux picture coming up and within a few seconds, you will have X up and running . The LCD screen is touch sensitive and you can use a small `stylus' (geeks use finger nails!) to select applications and move through the graphical interface. If you want to have keyboard input, be prepared for some agonizing manipulations using the stylus and a `soft keyboard' which is nothing but a GUI program from which you can select single alphabets and other symbols.

Waiting for bash

GUI's are for kids. You are not satisfied till you see the trusted old bash prompt. Well, you don't have to try a lot. The Simputer has a serial port - attach the provided serial cable to it - the other end goes to a free port on your host Linux PC (in my case, /dev/ttyS1). Now fire up a communication program (I use `minicom') - you have to first configure the program so that it uses /dev/ttyS1 with communication speed set to 115200 (that's what the Simputer manual says - if you are using a similar handheld, this need not be the same) and 8N1 format, hardware and software flow controls disabled. Doing this with minicom is very simple - invoke it as:

minicom -m -s

Once configuration is over - just type:

minicom -m

and be ready for the surprise. You will immediately see a login prompt. You should be able to type in a user name/password and log on. You should be able to run simple commands like `ls', `ps' etc - you may even be able to use `vi' .

If you are not familiar with running communication programs on Linux, you may be wondering what really happened. Nothing much - it's standard Unix magic. A program sits on the Simputer watching the serial port (the Simputer serial port, called ttySA0) - when you run minicom on the Linux PC, you establish a connection with that program, which sends you a login prompt over the line, reads in your response, authenticates you and spawns a shell with which you can interact over the line.

Once minicom initializes the serial port on the PC end, you can `script' your interactions with the Simputer. You are exploiting the idea that the program running on the Simputer is watching for data over the serial line - the program does not care whether the data comes from minicom itself or a script. You can try out the following experiment:

1. Open two consoles (on the Linux PC)
2. Run minicom on one console, log on to the simputer
3. On the other console, type `echo ls > /dev/ttyS1'
4. Come to the first console - you will see that the command `ls' has executed on the Simputer.

Setting up USB Networking

The Simputer comes with a USB slave port. You can establish a TCP/IP link between your Linux PC and the Simputer via this USB interface. Here are the steps you should take:

1. Make sure you have a recent Linux distribution - Red Hat 7.3 is good enough.
2. Plug one end of the USB cable onto the USB slave slot in the Simputer, then boot the Simputer.
3. Boot your Linux PC. DO NOT connect the other end of the USB cable to your PC now. Log in as root on the PC.
4. Run the command `insmod usbnet' to load a kernel module which enables USB networking on the Linux PC. Verify that the module has been loaded by running `lsmod'.
5. Now plug the other end of the USB cable onto a free USB slot of the Linux PC. The USB subsystem in the Linux kernel should be able to register a device attach. On my Linux PC, immediately after plugging in the USB cable, I get the following kernel messages (which can be seen by running the command `dmesg'):

usb.c: registered new driver usbnet
hub.c: USB new device connect on bus1/1, assigned device
number 3
usb.c: ignoring set_interface for dev 3, iface 0, alt 0
usb0: register usbnet 001/003, Linux Device

After you have reached this far, you have to run a few more commands:

1. Run `ifconfig usb0 192.9.200.1' - this will assign an IP address to the USB interface on the Linux PC.
2. Using `minicom' and the supplied serial cable, log on to the Simputer as root. Then run the command `ifconfig usbf 192.9.200.2' on the Simputer.
3. Try `ping 192.9.200.2' on the Linux PC. If you see ping packets running to and fro, congrats. You have successfully set up a TCP/IP link!

Hello, Simputer

It's now time to start real work. Your C compiler (gcc) normally generates `native' code, ie, code which runs on the microprocessor on which gcc itself runs - most often, an Intel (or clone) CPU. If you wish your program to run on the Simputer (which is based on the StrongArm microprocessor), the machine code generated by gcc should be understandable to the StrongArm CPU - your `gcc' should be a cross compiler. If you download the gcc source code (preferably 2.95.2) together with `binutils', you should be able to configure and compile it in such a way that you get a cross compiler (which could be invoked like, say, arm-linux-gcc). This might be a bit tricky if you are doing it for the first time - your handheld vendor should supply you with a CD which contains the required tools in a precompiled form - it is recommended that you use it (but if you are seriously into embedded development, you should try downloading the tools and building them yourselves).

Assuming that you have arm-linux-gcc up and running, you can write a simple `Hello, Simputer' program, compile it into an `a.out', ftp it onto the Simputer and execute it (it would be good to have one console on your Linux PC running ftp and another one running telnet - as soon as you compile the code, you can upload it and run it from the telnet console - note that you may have to give execute permission to the ftp'd code by doing `chmod u+x a.out' on the Simputer).

A note on the Arm Linux kernel

The Linux kernel is highly portable - all machine dependencies are isolated in directories under the `arch' subdirectory (which is directly under the root of the kernel source tree, say, /usr/src/linux). You will find a directory called `arm' under `arch'. It is this directory which contains ARM CPU specific code for the Linux kernel.

The Linux ARM port was initiated by Russell King. The ARM architecture is very popular in the embedded world and there are a LOT of different machines with fantastic names like Itsy, Assabet, Lart, Shannon etc all of which use the StrongArm CPU (there also seem to be other kinds of ARM CPU's - now that makes up a really heady mix). There are minor differences in the architecture of these machines which makes it necessary to perform `machine specific tweaks' to get the kernel working on each one of them. The tweaks for most machines are available in the standard kernel itself, and you only have to choose the actual machine type during the kernel configuration phase to get everything in order. But to make things a bit confusing with the Simputer, it seems that the tweaks for the initial Simputer specification have got into the ARM kernel code - but the vendors who are actually manufacturing and marketing the device seem to be building according to a modified specification - and the patches required for making the ARM kernel run on these modified configurations is not yet integrated into the main kernel tree. But that is not really a problem, because your vendor will supply you with the patches - and they might soon get into the official kernel.

Getting and building the kernel source

You can download the 2.4.18 kernel source from the nearest Linux kernel ftp mirror. You will need the file `patch-2.4.18-rmk4' (which can be obtained from the ARM Linux FTP site ftp.arm.linux.org.uk). You might also need a vendor supplied patch, say, `patch-2.4.18-rmk4-vendorstring'. Assume that all these files are copied to the /usr/local/src directory.

1. First, untar the main kernel distribution by running `tar xvfz kernel-2.4.18.tar.gz'
2. You will get a directory called `linux'. Change over to that directory and run `patch -p1 < ../patch-2.4.18-rmk4'.
3. Now apply the vendor supplied patch. Run `patch -p1 < ../patch-2.4.18-rmk4-vendorstring'.

Now, your kernel is ready to be configured and built. Before that, you have to examine the top level Makefile (under /usr/local/src/linux) and make two changes - there will be a line of the form:

ARCH := <lots-of-stuff>

near the top. Change it to

ARCH := arm

You need to make one more change. You observe that the Makefile defines:

AS = ($CROSS_COMPILE)as
LD = ($CROSS_COMPILE)ld
CC = ($CROSS_COMPILE)gcc

You note that the symbol CROSS_COMPILE is equated with the empty string. During normal compilation, this will result in AS getting defined to `as', CC getting defined to `gcc' and so on which is what we want. But when we are cross compiling, we use arm-linux-gcc, arm-linux-ld, arm-linux-as etc. So you have to equate CROSS_COMPILE with the string arm-linux-, ie, in the Makefile, you have to enter:

CROSS_COMPILE = arm-linux-

Once these changes are incorporated into the Makefile, you can start configuring the kernel by running `make menuconfig' (note that it is possible to do without modifying the Makefile. You run `make menuconfig ARCH=arm'). It may take a bit of tweaking here and there before you can actually build the kernel without error. You will not need to modify most things - the defaults should be acceptable.

1. You have to set the system type to SA1100 based ARM system and then choose the SA11x0 implementation to be `Simputer(Clr)' (or something else, depending on your machine). I had also enabled SA1100 USB function support, SA11x0 USB net link support and SA11x0 USB char device emulation.
2. Under Character devices->Serial drivers, I enabled SA1100 serial port support, console on serial port support and set the default baud rate to 115200 (you may need to set differently for your machine).
3. Under Character devices, SA1100 real time clock and Simputer real time clock are enabled.
4. Under Console drivers, VGA Text console is disabled.
5. Under General Setup, the default kernel command string is set to `root=/dev/mtdblock2 quite'. This may be different for your machine.

Once the configuration process is over, you can run

make zImage

and in a few minutes, you should get a file called `zImage' under arch/arm/boot. This is your new kernel.

Running the new kernel

I describe the easiest way to get the new kernel up and running.

Just like you have LILO or Grub acting as the boot loader for your Linux PC, the handheld too will be having a bootloader stored in its non volatile memory. In the case of the Simputer, this bootloader is called `blob' (which I assume is the boot loader developed for the Linux Advanced Radio Terminal Project, `Lart'). As soon as you power on the machine, the boot loader starts running - If you start minicom on your Linux PC, keep the `enter' key pressed and then power on the device, the bootloader, instead of continuing with booting the kernel stored in the device's flash memory, will start interacting with you through a prompt which looks like this:

blob>

At the bootloader prompt, you can type:

blob> download kernel

which results in blob waiting for you to send a uuencoded kernel image through the serial port. Now, on the Linux PC, you should run the command:

uuencode zImage /dev/stdout > /dev/ttyS1

This will send out a uuencoded kernel image through the COM port - which will be read and stored by the bootloader in the device's RAM. Once this process is over, you get back the boot loader prompt. You just have to type:

blob> boot

and the boot loader will run the kernel which you have right now compiled and downloaded.

A bit of kernel hacking

What good is a cool new device if you can't do a bit of kernel hacking? My next step after compiling and running a new kernel was to check out how to compile and run kernel modules. Here is a simple program called `a.c':

#include <linux/module.h>
#include <linux/init.h>

/* Just a simple module */

int 
init_module(void) 
{ 
   printk("loading module...\n");
   return 0;
}

void 
cleanup_module(void) 
{ 
   printk("cleaning up ...\n");
}

You have to compile it using the command line:

arm-linux-gcc -c -O -DMODULE -D__KERNEL__ a.c -I/usr/local/src/linux-2.4.18/include

You can ftp the resulting `a.o' onto the Simputer and load it into the kernel by running:

insmod ./a.o

You can remove the module by running:

rmmod a

Handling Interrupts

After running the above program, I started scanning the kernel source to identify the simplest code segment which would demonstrate some kind of physical hardware access - and I found it in the hard key driver. The Simputer has small buttons which when pressed act as the arrow keys - these buttons seem to be wired onto the general purpose I/O pins of the ARM CPU (which can also be configured to act as interrupt sources - if my memory of reading the StrongArm manual is correct). Writing a kernel module which responds when these keys are pressed is a very simple thing - here is a small program which is just a modified and trimmed down version of the hardkey driver - you press the button corresponding to the right arrow key - an interrupt gets generated which results in the handler getting executed. Our handler simply prints a message and does nothing else. Before inserting the module, we must make sure that the kernel running on the device does not incorporate the default button driver code - checking /proc/interrupts would be sufficient.

Compile the program shown below into an object file (just as we did in the previous program), load it using `insmod', check /proc/interrupts to verify that the interrupt line has been acquired. Pressing the button should result in the handler getting called - the interrupt count displayed in /proc/interrupts should also change.

#include <linux/module.h>
#include <linux/ioport.h>
#include <linux/sched.h>
#include <asm-arm/irq.h>
#include <asm/io.h>

static void 
key_handler(int irq, void *dev_id, struct pt_regs *regs)
{
  printk("IRQ %d called\n", irq);
}

static int  
init_module(void)
{
  unsigned int res = 0;
  printk("Hai, Key getting ready\n");
  set_GPIO_IRQ_edge(GPIO_GPIO12, GPIO_FALLING_EDGE);
  res = request_irq(IRQ_GPIO12, key_handler, SA_INTERRUPT,
  "Right Arrow Key", NULL);
  if(res) {
     printk("Could Not Register irq %d\n", IRQ_GPIO12);
     return res;
   }
  return res ;
}

static void 
cleanup_module(void)
{
  printk("cleanup called\n");
  free_irq(IRQ_GPIO12, NULL);
}

Future work

A Linux based handheld offers a lot of opportunities for serious fun - as I learn more about the device, I shall try to share my findings with the readers.

References

1. Simputer Project Home Page.
2. Simputerland and PicoPeta - information about Simputer development activities from companies which are manufacturing and marketing the product.
3. Arm Linux Project Home Page
4. Lart Project Home Page. Lots of cool stuff here. You might like to check out the `Clock Scaling' link on this site. Clock scaling allows you to change the clock speed of the running processor on the fly - useful for saving battery power.

I am an instructor working for IC Software in Kerala, India. I would have loved becoming an organic chemist, but I do the second best thing possible, which is play with Linux and teach programming!

...making Linux just a little more fun!

Qubism By Jon "Sir Flakey" Harsem

These cartoons are scaled down to minimize horizontal scrolling. To see a panel in all its clarity, click on it.

All Qubism cartoons are here at the CORE web site.

Jon is the creator of the Qubism cartoon strip and current Editor-in-Chief of the CORE News Site. Somewhere along the early stages of his life he picked up a pencil and started drawing on the wallpaper. Now his cartoons appear 5 days a week on-line, go figure. He confesses to owning a Mac but swears it is for "personal use".

...making Linux just a little more fun!

Yacc/Bison - Parser Generators - Part 1 By Hiran Ramankutty

Introduction

Yacc ("Yet Another Compiler Compiler") is used to parse a language described by a context-free grammar. Not all context-free languages can be handled by Yacc or Bison and only those that are LALR(1) can be parsed. To be specific, this means that it must be possible to tell how to parse any portion of an input string with just a single token of look-ahead. I will explain that clearly later in this article.

Bison is also a parser generator in the style of Yacc. It was written primarily by Robert Corbett and Richard Stallman made it Yacc compatible. There are differences between Bison and Yacc, but that is not the purpose of this article.

Languages and Context-Free Grammars

Grammar can be associated with English language as a set of rules to construct meaningful sentences. We can say the same for context-free grammars. Almost all programming languages are based on context-free grammars. The set of rules in any grammar will deal with syntactic groupings that will help in the construction of semantic structures. To be specific, it means that we specify one or more syntactic groupings and give rules for constructing them from their parts. For example in C: `expression' is one kind of grouping. One rule for making an expression is, "An expression can be made of a minus sign and another expression". Another would be, "An expression is an integer". You must have noticed that the rules are recursive. In fact, every such grammar must then have a rule which leads out of the recursion.

The most common formal system for representing such rules is the Backus-Naur Form or "BNF". All BNF grammars are context-free grammars.

In the grammatical rules for a language, we name a grouping as a symbol. Those symbols which can be sub-divided into smaller constructs are called non-terminals and those which cannot be subdivided are called terminals. If a piece of input is a single terminal then it is called a token and if it is a single nonterminal it is called a grouping. For example: `identifier', `number', `string' are distinguished as tokens, Whereas `expression', `statement', `declaration' and `function definition' are groupings in C language. Now, the full grammar may use additional language constructs with another set of nonterminal symbols.

Basic Parsing Techniques

A parser for grammar G determines whether an input string say `w' is a sentence of G or not. If `w' is a sentence of G then the parser produces the parse tree for `w' otherwise, an error message is produced. By parse tree we mean a diagram that represents the syntactic structure of a string `w'. There are two basic types of parsers for context-free grammars - bottom-up and top-down, the former one being of our interest.

Bottom-Up Parsing

It is also known as Shift-Reduce Parsing. Here, attempts to construct a parse tree for an input begin at the leaves (bottom) and work up towards the root (top). In other words this will lead to a process of `reduction' of the input string to the start symbol of the grammar based on its production rules. For example, consider the grammar:

S -> aAcBe
A -> Ab/b
B -> d

Let w = "abbcde". Our aim is to reduce this string `w' to S, where S is the start symbol. We scan "abbcde" looking for substrings that match the right side of some production. The substrings `b' and `d' qualify. Again there are 2 b's to be considered. Let us proceed with leftmost `b'. We replace it by `A' the left side of the production A -> b. The string has now become "aAbcde". We now see that `Ab', `b' and `d' each match the right side of some production. This time we will choose to replace `Ab' by `A', the left side of the production A -> Ab. The string now becomes "aAcde". Then replacing `d' by `B', the left side of the production B -> d, we obtain "aAcBe". The entire string can now be replaced by S.

Basically, we are replacing the right side of a production by the left side the process being called a reduction. Quite easy! Not always. It sometimes so happen that, the substring that we choose to reduce may produce a string which is not decomposable to the start symbol S.

Stack Implementation of Shift-Reduce Parsing

A convenient way to implement a shift-reduce parser is to use a stack and an input buffer. Let `$' symbol mark the bottom of the stack and the right end of the input.

The main concept is to shift the input symbols onto the stack until a handle b is on top of the stack. Now we reduce b to the left side of the appropriate production. The parser repeats this cycle until it has detected an error or until the stack contains the start symbol and the input is empty:

In fact, there are four possible actions that a shift-reduce parser can make and they are;

1. In a shift action, the next input symbol is shifted to the top of the stack.
2. In a reduce action, the parser knows that the right end of the handle is at the top of the stack. It must then locate the left end of the handle within the stack and decide with what nonterminal to replace the handle.
3. In an accept action, the parser announces successful completion of parsing.
4. In an error action, the parser discovers that a syntax error has occurred and calls an error recovery routine.

Let us see how these concepts are put into action in the example below.

Consider the grammar below:

E -> E + E
E -> E * E
E -> (E)
E -> id

Let the input string be id₁ + id₂ * id₃

Figure 1

Constructing a Parse Tree

The bottom-up tree construction process has two aspects.

1. When we shift an input symbol a onto the stack we create a one-node tree labeled a. Both the root and the yield of this tree are a, and the yield truly represents the string of terminals "reduced" (by zero reductions) to symbol a.
2. When we reduce X₁X₂... X_n to A, we create a new node labeled A. Its children, from left to right, are the roots of the trees for X₁,X₂,...,X_n. If for all iⁱ the tree for X_i has yield x_i, then the yield for the new tree is x₁x₂...x_n. This string has in fact been reduced to A by a series of reductions culminating in the present one. As a special case, if we reduce E to A we create a node labeled A with one child labeled E.

LR Parsing Algorithm

Construction of LALR parser requires the basic understanding of constructing an LR parser. LR parser gets its name because it scans the input from left-to-right and constructs a rightmost derivation in reverse.

A parser generates a parsing table for a grammar. The parsing table consists of two parts, a parsing action function ACTION and a goto function GOTO.

An LR parser has an input, a stack, and a parsing table. The input is read from left to right, one symbol at a time. The stack contains a string of the form s₀X₁s₁...X_ms_m where s_m is on top. Each X_i is a grammar symbol and each s_i is a symbol called a state. Each state symbol summarizes the information contained in the stack below it and is used to guide the shift-reduce decision.

The function ACTION stores values for s_m that is topmost stack element and a_i that is the current input symbol. The entry ACTION[s_m, a_i] can have one of four values:

1. shift s
2. reduce A -> B
3. accept
4. error

The function GOTO takes a state and grammar symbol as arguments and produces a state. Somewhat analogous to the transition table of a deterministic finite automaton whose input symbols are the terminals and nonterminals of the grammar.

A configuration of an LR parser is a pair whose first component is the stack contents and whose second component is the unexpended input:

(s₀ X₁ s₁ . . . X_m s_m, a_i a_i+1 . . . a_n$)

The next move of the parser is determined by reading a_i, the current input symbol, and s_m the state on top of the stack, and then consulting the action table entry ACTION[s_m, a_i]. The four value mentioned above for action table entry will produce four different configurations as follows:

1. If ACTION[s_m, a_i] = shift s, the parser executes a shift move, entering the configuration

   (s₀ X₁ s₁ . . . X_m s_m a_i s, a_i+1 . . . a_n$)

   Here the configuration has shifted the current input symbol a_i and the next state s = GOTO[s_m, a_i] onto the stack; a_i+1 becomes the new current input symbol.
2. If ACTION[s_m, a_i] = reduce A - > B,then the parser executes a reduce a move, entering the configuration

   (s₀ X₁ s₁ . . . X_m-r s_m-r A s, a_i a_i+1 . . . a_n$)

   where s = GOTO[s_m-r, A] and r is the length of B, the right side of the production. Here the first popped 2r symbols off the stack (r state symbols and r grammar symbols), exposing state s_m-r. The parser then pushed both A, the left side of the production, and s, the entry for ACTION[s_m-r, A], onto the stack. The current input symbol is not changed in a reduce move. Specifically, X_m-r+1 . . . X_m, the sequence of grammar symbols are popped off the stack and will always match B, the right side of the reducing production.
3. If ACTION[s_m, a_i] = accept, parsing is completed.
4. If ACTION[s_m, a_i] = error, the parser has discovered an error and calls an error recovery routine.

The LR parsing algorithm is simple. Initially the LR parser is in the configuration (s₀, a₁a₂...a_n$) where s₀ is a designated intial state and a₁a₂...a_n is the string to be parsed. Then the parser executes moves until an accept or error action is encountered.

I mentioned earlier that the GOTO function is essentially the transition table of a deterministic finite automaton whose input symbols (terminals and nonterminals) and a state when taken as arguments produce another state. Hence the GOTO function can be represented by a graph (directed) like scheme, where each node or state will be a set of items with elements that are productions in the grammar. The elements comprise the core of the items. The edges representing the transition will be labeled with the symbol for which the transition from one state to another is predetermined.

In the LALR (lookahead-LR) technique, LR items with common core are coalesced, and the parsing actions are determined on the basis of the new GOTO function generated. The tables obtained are considerably smaller than the LR tables, yet most common syntactic constructs of programming languages can be expressed conveniently by LALR grammar.

I am not going deep into construction of tables. Instead, I would like to explain the use of a tool called Yacc for parser generation.

Calculator Using Yacc

Input to Yacc can be divided into three sections:

1. definitions sections that consists of token declarations, and C code bracketed by "%{" and "}%"
2. the BNF grammar in the rules section
3. and user subroutines in the subroutines section.

We shall illustrate that by designing a small calculator that can add and subtract numbers. Let us start with the definitions section for the Yacc input file:

/* File name - calc1.l*/
%{ 
	#include "y.tab.h"
	#include < stdlib.h >
	void yyerror(char *);
}%

%%

[0-9]+	{
		yylval = atoi(yytext);
		return INTEGER;
	}

[-+\n]	{
		return *yytext;
	}

[ \t]	;	/*skip whitespace*/

.	yyerror("Unknown character");

%%

int yywrap(void) {
	return 1;
}

Yacc when run generates a parser in the file y.tab.c, along side which another file y.tab.h is also generated. Lex includes this file and utilizes the definitions for token values. Lex returns the values associated with the tokens in variable yylval. But to get tokens, yacc calls yylex the return value of which is integer.

The yacc input specification is given below:

/* file name calc1.y */
%{
    int yylex(void);
    void yyerror(char *);
%}

%token INTEGER

%%

program:
        program expr '\n'         { printf("%d\n", $2); }
        |
        ;

expr:
        INTEGER
        | expr '+' expr           { $$ = $1 + $3; }
        | expr '-' expr           { $$ = $1 - $3; }
        ;

%%

void yyerror(char *s) {
    fprintf(stderr, "%s\n", s);
}

int main(void) {
    yyparse();
    return 0;
}

Here, the grammar is specified using productions. Left hand side of a production being a non terminal followed by a colon and then the right hand side of a production. The contents of the braces show the action associated with the productions. So what does the rules say ?

It says that a program consists of zero or more expressions. Each expression terminates with a newline. When a newline is detected, we print the value of the expression.

Now execute yacc as shown:

yacc -d calc1.l

You get a message "shift/reduce conflict". Shift/reduce conflict arises when the grammar is ambiguous and there is a possibility of more than one derivation tree. To understand this, consider the example given in the stack implementation of shift-reduce parsing. In step 6, instead of shifting we could have reduced appropriately as per the grammar . Then addition will have higher precedence over multiplication.

Before proceeding you must know about another kind of conflict that is reduce-reduce conflict. This arises when there are more than one option for reducing a stack symbol. For example: In the grammar below id can be reduced to T or E.

E -> T
E -> id
T -> id

Yacc takes a default action when conflicts arise. When there is shift-reduce conflict, yacc will shift and when there is reduce-reduce conflict, it will use the first rule in the listing. Yacc also issues a warning message when conflicts arise. Warnings can be eliminated by making the grammar unambiguous.

Coming back, yacc produces two files; y.tab.c and y.tab.h. Some lines one has to notice are:

#ifndef YYSTYPE
typedef int YYSTYPE
#endif
#define INTEGER 257
YYSTYPE yylval

Internally, yacc maintains two stacks in memory; a parse stack and a value stack. The current parsing state is determined by the terminals and/or non terminals that are present in the parse stack. The value stack is always synchronized and holds an array of YYSTYPE elements, which associates a value with each element in the parse stack. So for example, when lex returns an INTEGER token, yacc shifts this token to the parse stack. At the same time, the corresponding yylval is shifted to the value stack. This makes it easier in finding the value of a token at any given time.

So when we apply the rule

expr: expr '+' expr	{ $$ = $1 + $3; }

we pop "expr '+' expr" and replace it by "expr". In other words we replace the right hand side of a production by left hand side of the same production. Here we pop three terms off the stack and push back one term. The value stack will contain "$1" for the first term on the right-hand side of the production, "$2" for the second and so on. "$$" designates the top of the stack after reduction has taken place. The above action adds the values associated with two expressions, pops three terms off the value stack, and pushes back a single sum. Thus the two stacks remain synchronized and when a newline is encountered, the value associated with expr is printed.

The last function that we need is a 'main'. But the grammar is ambiguous and yacc will issue shift-reduce warnings and will process the grammar using shift as the default operation.

I am not giving the function here because there is more to learn. I shall come up with that in the next part. I shall also explain how to remove ambiguity from the grammar and then design the calculator for it. In fact, some more funcionalities shall be incorporated into the grammar to have a better understanding.

I am a final year student of Computer Science at Government Engineering College, Trichur, Kerala, India. Apart from Linux I enjoy reading books on theoretical physics.

...making Linux just a little more fun!

I Built a Custom Debian CD from Knoppix By Sunil Thomas Thonikuzhiyil

Introduction

    Knoppix is a live cd distribution based on debian GNU/Linux.It contains a large number of applications which can come in handy even on minimal hardware.Knoppix supports alarge number of graphics cards sound cards scsi and USB devices.It can be used as a Linux demo, educational cd, rescue system or adapted and used as a platform for commercial product demo. It is not necesary to install anything to hard disk There is an installation program which can install the entire cd to a hard disk, if you like. It means that you have a full fledged debian installation in 20 minutes. This document describes how I built a custom live cd from knoppix. My primary motivation to build this cd was to include some of my favorite applications which are missing from stock knoppix CD.  If you find any errors in this document please drop me a mail here

Requirements

a) Software

To start with you have to download knoppix image from knoppix site. There is a release every one  or two week. There are 2 images: German and English. I did my setup based on 31-10-2002-EN release.

  If you already have an image you can try to rsync it to the most recent version as below. However don't expect much bandwidth saving since the knoppix image is compressed. If you have a knoppix cdrom create an image by   #dd if=/dev/cdrom of=knoppix.iso)

Rename the Knoppix iso image to reflect the current release name.
  Example
  I have downloaded KNOPPIX_V3.1-23-10-2002-EN.iso
  I want to update it to   KNOPPIX_V3.1-31-10-2002-EN.iso
  Rename KNOPPIX_V3.1-23-10-2002-EN.iso to  KNOPPIX_V3.1-31-10-2002-EN.iso
 Then
 rsync -P --stats ftp.leo.org::Knoppix/KNOPPIX_V3.1-31-10-2002-EN.iso  .
( you can use any other rsync site of knoppix. Always check the site for latest release)

b) Hardware

A Computer with tons of free hard disk space and memory. I did this on a Pentium 3 950MHZ machine with 128 mb RAM.

Initial setup

 Make a lot of  disk space free  You need a lot of real estate for re-mastering KNOPPIX  CD
   I made two fresh partitions  on my 20 GB Hard disk
           hda2 with 2GB  for swap
           hda3 with 5 GB for re-mastering work ( you can also  use an existing Linux partition if it has sufficient  free space)

 Now boot the machine with Knoppix cd ( You can also do the re-mastering after a  hard disk install of knoppix . A how to for hard disk install  can be found here )

   At boot prompt press enter. Knoppix now boots into GUI. The default is KDE . You  can change it at boot prompt if you want . I did re-mastering  while booted to KDE. It is assumed that you are somewhat familiar with Knoppix.  Read  Knoppix cheat codes on the CD  for more information on booting.

a) Configure networking from the KDE menu

    I am connected to a Lan and I configured IP address, netmask, name server and gateway This step is very important since you have to get the custom stuff to be installed from else where

b) Setup partitions

Open a root shell from KDE menu  (K/Knoppix/Root-shell)  You will get  # prompt

Run cfdisk

Next you have to make the necessary  partitions . I  created two partitions hda2 with 2 GB and  hda3 with 5 GB

Make the 2GB  partitions type as swap  ( /hda2 in my case)

Make the 5 GB partitions type as Linux native( ext2)  (hda3 here)
Save the modified partition information

Quit cfdisk

 For creating compressed file system we need a lot of swap space . I created the swap with
 # mkswap /dev/hda2
 # swapon /dev/hda2               

Create an ext2 file system on the 5GB partition
  # mke2fs /dev/hda3

Mount the 5GB  partition to the Knoppix file system
# mount /dev/hda3 /mnt/hda3

The basic setup for re-mastering is ready

Installing and Removing Software

The knoppix CD  is organized somewhat like the figure below ( Correct me if I am wrong. it may  look different when you look at it from windows or another Linux distro)

     
/--demos
|--talks
|--index.html
|--autorun.bat
|--autorun.inf
|--knoppix.ico
|--KNOPPIX
      |--KNOPPIX
      |--boot.img
      |--background.gif
      |- (Some more files here)

 The file KNOPPIX in  /KNOPPIX  directory on the cd is approxiamtley 700MB. The file contains a compressed image of the file system. We have to modify this file alone and can leave the rest of  the cd intact (unless you want to modify boot image startup files etc).

a) Copy Knoppix file system to hard disk

b) Chroot

 You have to install/uninstall software under this tree ( if you don't have networking copy your sources to  (say)  /mnt/hda3/KNOPPIX/root/  and if you have debs copy them to  /mnt/hda3/KNOPPIX/var/cache/apt/archives)
Now we are going to change the root of the file system to /mn/hda3/KNOPPIX
#chroot /mnt/hda3/KNOPPIX

you will get back # prompt ( If you get /dev/null  permission denied message here just press control C)
 You  are at   / ( chrooted to /mnt/hda3/KNOPPIX)

Next mount the proc file system
#mount -t proc /proc proc    

c) Setup networking

Verify your ip address now with ifconfig. (It should be same as what you have out side chroot) Then try  ping google.com. If you  can ping google.com your network setup  is ok under chroot.Do an apt get update 

d) Install/Uninstall

You can install /uninstall whatever software you  need using apt. Since the original Cd has a lot of software installed it may not be an easy task.The following is a partial list of packages I removed

 Games

Non -free

Misc  

 I copied the above list to a file ( say kicklist)  then did
    #dpkg -P `cat kicklist`  
It removed all files listed (notice the back quote above )

If you are looking for big installed packages
      #  dpkg-awk "Status: .* installed$" -- Package Installed-Size| awk '{print $2}' | egrep -v '^$' | xargs -n2 echo | perl -pe 's/(\S+)\s(\S+)/$2 $1/' | sort -rg
  will list the  packages  with size in descending order.

Finally run deborphan to check if there are any orphaned packages
#deborphan > /tmp/orphanlist
#dpkg -P `cat /tmp/orphanlist`
# rm /tmp/orphanlist 

An alternate method is to use  synaptic and add/remove packages from GUI. Synaptic is good graphical front end to apt

For this do
# apt-get install synaptic
You have to export DISPLAY environment variable for synaptic to work properly
#DISPLAY=myip:0.0    ( replace my ip with your actual IP)
#export DISPLAY
#synaptic

It will start synaptic
Enjoy apt through synaptic

Once you are finished with synaptic you can re master the cd. If you are  working from a hard disk install of knoppix  and want synaptic to work, look in/etc/X11/xinit/xserverrc  and see that -nolisten tcp is removed.Also do xhost + as a non root user)

Unmount proc  ( This is very important)
 #umount /proc

Press control D to leave chrooted environment

Further Customization  

 Download the software source inside chroot environment. Compile and install as usual . If it is an X11 application export display before you test
I use checkininstall asic-linux.com.mx/~izto/checkinstall/ to install and maintain home brew debs
Remember to remove the sources once you are finished (it will take up space on your CD).

It is possible to set password for users. Just set it under chrooted environment

/usr/local/lib/knoppix.gif is the default background image in X

 The Knoppix Cd uses syslinux to boot. If you want to change the boot screen/messages do the following. Make a temporary directory on your hard disk (I did mkdir /mnt/hda3/image)
 Copy the boot.img  file from  Knoppix  directory of your knoppix cd 
       #cp /KNOPPIX/boot.img /mnt/hda3
 Mount the image as follows
      # mount -t msdos -o loop   /mnt/hda3/boot.img  /mnt/hda3/image
  Now look in the image directory you created. There are a number of interesting  files in this directory

 
       #pngtopnm <logo.png >logo.pnm

       #ppmtolss16 <logo.pnm >logo.16

       # cp logo.16 /mnt/hda3/image/logo.16 
   

  (Keep the size of the final log.16 around 50 k). Unmount image directory. Copy the boot.img to a floppy
   #dd if=boot.img of=/dev/fd0
Boot the machine from the floppy you have made. If it boots up properly you are done

Make a  new custom kernel using kernel package . Keep the kernal size small. Copy the kernal to and modules to boot.img file. replace /lib/modules/2.4.19-xfs  with  modules of your new kernel
   Replace files in  /boot  

  Look for the following lines
---------------------------------------

#Also read desired desktop, if any

DESKTOP="$(getbootparam desktop 2>/dev/null)"

# Allow only supported windowmanagers

case "$DESKTOP" in gnome|kde|larswm|xfce|windowmaker|wmaker|icewm|fluxbox|twm) ;; *)

  DESKTOP="KDE"; ;; esac
--------      ^^   --------------------------------------

  Change the KDE above to gnome and that is all 

 (* link to the script goes here*)       

Re mastering the CD

 1)  Make a new directory on /mnt/hda3
   I called it NewCd
    Copy Everything except Compressed image file(KNOPPIX) from knoppix cd (look at /cdrom). You can safely delete the directories demos and  talks
  2) Create the compressed Image
   #mkisofs -R   /mnt/hda3/KNOPPIX  |  create_compressed_fs -   65536  > /mnt/hda3/NewCD/KNOPPIX/KNOPPIX   

 3) Recreate the bootable CD
 #cd /mnt/hda3

 #mkisofs -r -J -b KNOPPIX/boot.img -c KNOPPIX/boot.cat   -o myknoppix.iso  NewCd

Create a boot floppy
# dd if=/mnt/hda3/KNOPPIX/boot.img of=/dev/fd0 
Copy the compressed file you created to a directory /KNOPPIX on any partition. The boot floppy i will look for /KNOPPIX/KNOPPIX on hard disk partitions.This makes your testing easy. Once you are satisfied with your image burn itto a CD  

FAQ

 1) How do I  stop konquerer at startup
  To stop konquerers you  have to modify
        /etc/X11/Xsession.d/45xsession
    Look for the following lines

-------------------------------------------
if [ -e "$INDEXFILE" ]; then
cat >> $HOME/Desktop/KNOPPIX.desktop <<EOF
[Desktop Entry]
Name=KNOPPIX
Exec=kfmclient openProfile webbrowsing $INDEXFILE
Type=Application
Icon=html
Terminal=0
EOF
ln $HOME/Desktop/KNOPPIX.desktop $HOME/.kde/Autostart/showindex.desktop
fi

 It makes an autostart file. Comment it  out

2) I have booted knoppix cd and mounted a hard disk how do i copy something via scp to the hard disk
      Open a  shell
      set a password for user knoppix
      start ssh  (/etc/init.d/ssh start)
      Then copy with scp

 3 I am at $ prompt I want to su
      Do  sudo  passwd
      set a  root password
      then su

 4) default text mode boots up in frame buffer and characters are very small how do I fix it
     Mount boot.img
     look for syslinux.cfg
     under  Default  vmlinuz
     change VGA=791 to VGA=normal

5 )My keyboard lay out is  German.  How do i change it to English
 Open KDE control center select system ->keyboard and change it to US English

References

I work as consultant information technology at the Kerala Legislative Assembly Trivandrum India. I have been hooked on Linux since 1996. I have a Masters in Computer Science from Cochin University. I am interested in all sorts of operating systems. In my free time I love to listen to Indian classical music.

...making Linux just a little more fun!

Encryption using OpenSSL's crypto libraries By Vinayak Hegde

Motivation for the article

Linux has already made quite a few inroads into the corporate world. One of the persistent demands of the corporate world has been a need for better data security. This is where encryption comes in, to hide sensitive data from a third party intruder. Open-source software has a reputation for secure programming. This article is another step in that direction.

OpenSSL's libcrypto is a really good library if you want to use encryption without bothering with the details of underlying implementation of the algorithm. The problem is that the documentation is really minimal. You can obviously read the source and figure out what going on. Also the fact that function names are intuitive helps to some extent. Another way of getting help is joining the various mailing lists from the OpenSSL website. However the command line tools of OpenSSL are pretty well documented and easy to use. I shall explain in this article how to use the blowfish algorithm for encryption using OpenSSL's crypto libraries.

Some Background Information

During the early days of cryptography, algorithms as well as keys were secret. However now that trend has changed. Now algorithms are publicly known and keys are kept secret. The best example of this is the RSA algorithm which is widely known and implemented. The public key are known to the world but the private keys are kept secret. RSA is an asymmetric algorithm as it does not use the same key for encryption and decryption. Also it is generally not advisable to use RSA for encrypting large amounts of data as the it is computationally intensive.

For encrypting large amounts of data, generally less computationally intensive algorithms are prefered. In this article we use the blowfish algorithm for encrypting and decrypting data. Blowfish is a symmetric algorithm which means it uses the same key for encryption and decryption. Blowfish was designed by the famous cryptographer Bruce Schneier. Blowfish is a fast algorithm for encryption/decryption.

Generating the key

For the purposes of demonstration we shall use a 128-bit key. This is stored as an character array in the program. We also generate an 64 bit initialization vector(IV). For our program we will use Cipher Block Chaining (CBC) mode. Also we will not use the blowfish functions directly but use then through a the higher level interface.

An initialization vector is a bit of random information that is used as an input in chained encryption algorithms, that is, when each stage of encrypting a block of input data provides some input to the encryption of the next block. (blowfish uses 64-bit blocks for encryption). The IV provides the first bit of input for encrypting the 1st block of data, which then provides input for the 2nd block and so on. The bit left over at the end is discarded.

The random bits are generated from the character special file /dev/random which provides a good source for random numbers. See the manpage for more information.

int
generate_key ()
{
	int i, j, fd;
	if ((fd = open ("/dev/random", O_RDONLY)) == -1)
		perror ("open error");

	if ((read (fd, key, 16)) == -1)
		perror ("read key error");

	if ((read (fd, iv, 8)) == -1)
		perror ("read iv error");
	
	printf("128 bit key:\n");
	for (i = 0; i < 16; i++)
		printf ("%d \t", key[i]);
	printf ("\n ------ \n");

	printf("Initialization vector\n");
	for (i = 0; i < 8; i++)
		printf ("%d \t", iv[i]);

	printf ("\n ------ \n");
	close (fd);
	return 0;
}

The Encryption routine

The encryption routine takes two parameters - the file descriptors of input file and the output file to which the encrypted data is to be saved. It is always a good idea to zero-fill your buffers using the memset or bzero commands before using the buffers with data. This is especially important if you plan to reuse the buffers. In the program below, the input data is being encrypted in blocks of 1K each.

The steps for encryption are as follows :-

1. Create a cipher context
2. Initialize the cipher context with the values of Key and IV
3. Call EVP_EncryptUpdate to encrypt successive blocks of 1k eack
4. Call EVP_EncryptFinal to encrypt "leftover" data
5. Finally call EVP_CIPHER_CTX_cleanup to discard all the sensitive information from memory

You may be wondering what "leftover" data is? As mentioned earlier, Blowfish encrypts information in blocks of 64-bit each. Sometimes we may not have 64 bits to make up a block. This may happen if the buffer size in the program below or the file/input data size is not a integral multiple of 8 bytes(64-bits).So accordingly the data is padded and then the partial block is encrypted using EVP_EncryptFinal. The length of the encoded data block is stored in the variable tlen and added to the final length.

int
encrypt (int infd, int outfd)
{
	unsigned char outbuf[OP_SIZE];
	int olen, tlen, n;
	char inbuff[IP_SIZE];
	EVP_CIPHER_CTX ctx;
	EVP_CIPHER_CTX_init (& ctx);
	EVP_EncryptInit (& ctx, EVP_bf_cbc (), key, iv);

	for (;;)
	  {
		  bzero (& inbuff, IP_SIZE);

		  if ((n = read (infd, inbuff, IP_SIZE)) == -1)
		    {
			    perror ("read error");
			    break;
		    }
		  else if (n == 0)
			  break;

		  if (EVP_EncryptUpdate (& ctx, outbuf, & olen, inbuff, n) != 1)
		    {
			    printf ("error in encrypt update\n");
			    return 0;
		    }

		  if (EVP_EncryptFinal (& ctx, outbuf + olen, & tlen) != 1)
		    {
			    printf ("error in encrypt final\n");
			    return 0;
		    }
		  olen += tlen;
		  if ((n = write (outfd, outbuf, olen)) == -1)
			  perror ("write error");
	  }
	EVP_CIPHER_CTX_cleanup (& ctx);
	return 1;
}

The Decryption routine

The decryption routine basically follows the same steps as the encryption routine. The following code show how the decryption is done.

int decrypt (int infd, int outfd) { unsigned char outbuf[IP_SIZE]; int olen, tlen, n; char inbuff[OP_SIZE]; EVP_CIPHER_CTX ctx; EVP_CIPHER_CTX_init (& ctx); EVP_DecryptInit (& ctx, EVP_bf_cbc (), key, iv); for (;;) { bzero (& inbuff, OP_SIZE); if ((n = read (infd, inbuff, OP_SIZE)) == -1) { perror ("read error"); break; } else if (n == 0) break; bzero (& outbuf, IP_SIZE); if (EVP_DecryptUpdate (& ctx, outbuf, & olen, inbuff, n) != 1) { printf ("error in decrypt update\n"); return 0; } if (EVP_DecryptFinal (& ctx, outbuf + olen, & tlen) != 1) { printf ("error in decrypt final\n"); return 0; } olen += tlen; if ((n = write (outfd, outbuf, olen)) == -1) perror ("write error"); } EVP_CIPHER_CTX_cleanup (& ctx); return 1; }

The complete code

A minimal interactive program implementing the above routines can be downloaded from here . The command for compiling the program is

# gcc -o blowfish sym_funcs.c -lcrypto

The program takes three files from the command line

1. File to be encrypted
2. File is which the encrypted data is to be stored
3. File in which decrypted data is to be stored

An Example Application - A Secure Instant Messenger

Consider an instant messenger software (IM) which wants to communicate with another IM securely. The following approach could be followed.

1. Each IM client has it's own public and private key.
2. The IM client has the public keys of all the IMs it wants to communicate with. (say friends' IMs).
3. The session key is generated by the client which initiates the connection. This session key is used for encrypting the messages between the two clients.
4. The session key is encrypted and exchanged between two/multiple clients using public-Key encryption.(eg. RSA algorithm). Thus Authentication is also taken care of.
5. The exchange of encrypted data (using Blowfish symmetric encryption) thereafter takes place between the different clients after this "security handshake".

Resources

1. OpenSSL Homepage
2. The Blowfish Algorithm
3. Handbook of Applied Cryptography

My life changed since I discovered Linux. Suddenly Computers became interesting as i could try out lots of stuff on my Linux box due to the easy availabily of source code. My interests are predominantly in the fields of networking, embedded systems and programming languages. I currently work for Aparna Web services where we make Linux accessible for academia/corporations by configuring remote boot stations (Thin Clients).

...making Linux just a little more fun!

The Back Page

The Nigeria scams riled up one person enough to write a parody spam.

X-Spam-Status: No, hits=4.3 required=5.0
	tests=BILLION_DOLLARS,DEAR_SOMETHING,IN_REP_TO,ITS_LEGAL,
	      LINES_OF_YELLING,LINES_OF_YELLING_2,LINES_OF_YELLING_3,
	      NIGERIAN_TRANSACTION_1,NIGERIAN_TRANSACTION_2,REFERENCES,
	      SIGNATURE_SHORT_DENSE,SPAM_PHRASE_05_08,SUPERLONG_LINE,
	      UPPERCASE_75_100,USER_AGENT,USER_AGENT_MUTT,US_DOLLARS_3
	version=2.43
X-Spam-Level: ****

HIGHLY CONFIDENTIAL 

FROM: GEORGE WALKER BUSH 
DEAR SIR / MADAM, 

I AM GEORGE WALKER BUSH, SON OF THE FORMER PRESIDENT OF THE UNITED STATES OF
AMERICA GEORGE HERBERT WALKER BUSH, AND CURRENTLY SERVING AS PRESIDENT OF THE
UNITED STATES OF AMERICA. THIS LETTER MIGHT SURPRISE YOU BECAUSE WE HAVE NOT
MET NEITHER IN PERSON NOR BY CORRESPONDENCE. I CAME TO KNOW OF YOU IN MY SEARCH
FOR A RELIABLE AND REPUTABLE PERSON TO HANDLE A VERY CONFIDENTIAL BUSINESS
TRANSACTION, WHICH INVOLVES THE TRANSFER OF A HUGE SUM OF MONEY TO AN ACCOUNT
REQUIRING MAXIMUM CONFIDENCE. 

I AM WRITING YOU IN ABSOLUTE CONFIDENCE PRIMARILY TO SEEK YOUR ASSISTANCE IN
ACQUIRING OIL FUNDS THAT ARE PRESENTLY TRAPPED IN THE REPUBLIC OF IRAQ. MY
PARTNERS AND I SOLICIT YOUR ASSISTANCE IN COMPLETING A TRANSACTION BEGUN BY MY
FATHER, WHO HAS LONG BEEN ACTIVELY ENGAGED IN THE EXTRACTION OF PETROLEUM IN
THE UNITED STATES OF AMERICA, AND BRAVELY SERVED HIS COUNTRY AS DIRECTOR OF THE
UNITED STATES CENTRAL INTELLIGENCE AGENCY. 

IN THE DECADE OF THE NINETEEN-EIGHTIES, MY FATHER, THEN VICE-PRESIDENT OF THE
UNITED STATES OF AMERICA, SOUGHT TO WORK WITH THE GOOD OFFICES OF THE PRESIDENT
OF THE REPUBLIC OF IRAQ TO REGAIN LOST OIL REVENUE SOURCES IN THE NEIGHBORING
ISLAMIC REPUBLIC OF IRAN. THIS UNSUCCESSFUL VENTURE WAS SOON FOLLOWED BY A
FALLING OUT WITH HIS IRAQI PARTNER, WHO SOUGHT TO ACQUIRE ADDITIONAL OIL
REVENUE SOURCES IN THE NEIGHBORING EMIRATE OF KUWAIT, A WHOLLY-OWNED
U.S.-BRITISH SUBSIDIARY. 

MY FATHER RE-SECURED THE PETROLEUM ASSETS OF KUWAIT IN 1991 AT A COST OF
SIXTY-ONE BILLION U.S. DOLLARS ($61,000,000,000). OUT OF THAT COST, 
THIRTY-SIX BILLION DOLLARS ($36,000,000,000) WERE SUPPLIED BY HIS PARTNERS IN
THE KINGDOM OF SAUDI ARABIA AND OTHER PERSIAN GULF MONARCHIES, AND SIXTEEN
BILLION DOLLARS ($16,000,000,000) BY GERMAN AND JAPANESE PARTNERS. 

BUT MY FATHER'S FORMER IRAQI BUSINESS PARTNER REMAINED IN CONTROL OF THE
REPUBLIC OF IRAQ AND ITS PETROLEUM RESERVES. 

MY FAMILY IS CALLING FOR YOUR URGENT ASSISTANCE IN FUNDING THE REMOVAL OF THE
PRESIDENT OF THE REPUBLIC OF IRAQ AND ACQUIRING THE PETROLEUM ASSETS OF HIS
COUNTRY, AS COMPENSATION FOR THE COSTS OF REMOVING HIM FROM POWER. 

UNFORTUNATELY, OUR PARTNERS FROM 1991 ARE NOT WILLING TO SHOULDER THE BURDEN OF
THIS NEW VENTURE, WHICH IN ITS UPCOMING PHASE MAY COST THE SUM OF 100 BILLION
TO 200 BILLION DOLLARS ($100,000,000,000 - $200,000,000,000), BOTH IN THE
INITIAL ACQUISITION AND IN LONG-TERM MANAGEMENT. 

WITHOUT THE FUNDS FROM OUR 1991 PARTNERS, WE WOULD NOT BE ABLE TO ACQUIRE THE
OIL REVENUE TRAPPED WITHIN IRAQ. THAT IS WHY MY FAMILY AND OUR COLLEAGUES ARE
URGENTLY SEEKING YOUR GRACIOUS ASSISTANCE. OUR DISTINGUISHED COLLEAGUES IN THIS
BUSINESS TRANSACTION INCLUDE THE SITTING VICE-PRESIDENT OF THE UNITED STATES OF
AMERICA, RICHARD CHENEY, WHO IS AN ORIGINAL PARTNER IN THE IRAQ VENTURE AND
FORMER HEAD OF THE ALLIBURTON OIL COMPANY, AND CONDOLEEZA RICE, WHOSE
PROFESSIONAL DEDICATION TO THE VENTURE WAS DEMONSTRATED IN THE NAMING OF A
CHEVRON OIL TANKER AFTER HER. 

I WOULD BESEECH YOU TO TRANSFER A SUM EQUALING TEN TO TWENTY-FIVE PERCENT
(10-25 %) OF YOUR YEARLY INCOME TO OUR ACCOUNT TO AID IN THIS IMPORTANT
VENTURE. THE INTERNAL REVENUE SERVICE OF THE UNITED STATES OF AMERICA WILL
FUNCTION AS OUR TRUSTED INTERMEDIARY. I PROPOSE THAT YOU MAKE THIS TRANSFER
BEFORE THE FIFTEENTH (15TH) OF THE MONTH OF APRIL. 

 
I KNOW THAT A TRANSACTION OF THIS MAGNITUDE WOULD MAKE ANYONE APPREHENSIVE AND
WORRIED. BUT I AM ASSURING YOU THAT ALL WILL BE WELL AT THE END OF THE DAY. A
BOLD STEP TAKEN SHALL NOT BE REGRETTED, I ASSURE YOU. PLEASE DO BE INFORMED
THAT THIS BUSINESS TRANSACTION IS 100% LEGAL. IF YOU DO NOT WISH TO CO-OPERATE
IN THIS TRANSACTION, PLEASE CONTACT OUR INTERMEDIARY REPRESENTATIVES TO FURTHER
DISCUSS THE MATTER. 

I PRAY THAT YOU UNDERSTAND OUR PLIGHT. MY FAMILY AND OUR COLLEAGUES WILL BE
FOREVER GRATEFUL. PLEASE REPLY IN STRICT CONFIDENCE TO THE CONTACT NUMBERS
BELOW. 

SINCERELY WITH WARM REGARDS, 
GEORGE WALKER BUSH 

Happy Linuxing!

Mike ("Iron") Orr
Editor, Linux Gazette, gazette@ssc.com