Merge Sort in Bash

So, during spring break, I was extremely bored and implimented merge sort into a language that doesn’t really need it: Bash. I got inspiration to do this from seeing  merge sort implimented in Prolog. As of right now, it merely sorts integers, but can sort anything, given that a compareTo method of what you want sorted is written into the merge method (bash isn’t object oriented, so it’s not really so adaptable to adaptability.) I doubt I’m the first person to do this, but it’s a nice thought experiment to see how limited languages can still allow the performance of advanced operations. I don’t guarantee that this algorithm performs in n*log(n) time as I’m not sure of the individual costs of bash operations or the cost of reading and executing this, but I tested it with 1330 numbers and it sorted them in about 35 seconds on my 1.6 Ghz laptop.


#!/bin/bash

mrgsrt() {
# This function impliments the merge sort algorithm into bash.
#
# @Author: Adam Vite

if [ $# = 1 ]; then
echo $1;
# There is only one arguement, list is sorted
elif [ $# -gt 1 ]; then
i=0;
unset left;
unset right;
for x in $@ ; do
if [ $i -lt $(($# / 2)) ]; then
left=$( echo $left $x );
i=$(($i + 1));
else
right=$( echo $right $x );
fi;
done;
# The arguments have been split in half

left=$( mrgsrt $left );
right=$( mrgsrt $right );
# each half has been sorted recursively

mrg $left $right;
# The two halves have been merged together with a helper method
else
echo "Usage: mrgsrt <series of numbers seperated by spaces>";
fi;
}

mrg() {
# This method sorts two sorted lists of numbers by adding the lowest of
# firstmost unsorted number into a new list until all numbers have been
# added and then returns that list.
#
# @Author: Adam Vite

l=1; # Begining index of left half
r=$(($# / 2 + 1)); # Begining index of right half
unset list;
while [ $l -ne $(($# / 2 + 1)) ] || [ $r -ne $(($# + 1)) ]; do
if [ $l = $(($# / 2 + 1)) ]; then
list=$( echo $list ${!r} );
r=$(($r+1));
# Left half has been sorted

elif [ $r = $(($# + 1)) ]; then
list=$( echo $list ${!l} );
l=$(($l+1));

# Right half has been sorted

elif [ ${!l} -lt ${!r} ]; then
list=$( echo $list ${!l} );
l=$(($l+1));
# Firstmost unsorted left is less than firstmost unsorted right
else
list=$( echo $list ${!r} );
r=$(($r+1));
# Firstmost unsorted right is less than firstmost unsorted left
fi;
done;
echo $list;
}

Using Live CDs to help repair/diagnose a PC

When I work on a Windows machine, I usually end up coming across a missing/corrupt driver. On Windows it is next to impossible to figure out what kind of hardware is in your computer without having the driver installed. You could google for a device id, but you’re going to get a lot of wrong answers.

A better solution is using a live CD. Any recent one will work; the tools you’re using will work regardless.

lspci – List all PCI Devices

01:00.0 VGA compatible controller: nVidia Corporation GeForce 8400M GS (rev a1)
03:01.0 FireWire (IEEE 1394): Ricoh Co Ltd R5C832 IEEE 1394 Controller (rev 05)
03:01.1 Generic system peripheral [0805]: Ricoh Co Ltd R5C822 SD/SDIO/MMC/MS/MSPro Host Adapter (rev 22)
03:01.2 System peripheral: Ricoh Co Ltd R5C843 MMC Host Controller (rev 12)
03:01.3 System peripheral: Ricoh Co Ltd R5C592 Memory Stick Bus Host Adapter (rev 12)
03:01.4 System peripheral: Ricoh Co Ltd xD-Picture Card Controller (rev 12)
09:00.0 Ethernet controller: Broadcom Corporation NetLink BCM5906M Fast Ethernet PCI Express (rev 02)
0c:00.0 Network controller: Intel Corporation PRO/Wireless 3945ABG Network Connection (rev 02)

Want to know the model of your network card, even if Linux doesn’t support it? No quite sure what kind of nvidia card you have? Done.

You might say, “Well sure, that’s nifty. But what about USB devices?”

lsusb – List USB Devices

Bus 004 Device 002: ID 046d:c50e Logitech, Inc. MX-1000 Cordless Mouse Receiver

dmesg – Outputs nifty stuff about your computer

From hard drives, to being able to see if the machine detected a new USB device to what wireless cards were detected dmesg offers a ton of information. I suggest using grep and more; my dmesg is 541 lines long, and it wouldn’t be surprising for yours to be more.

It it also a great place to find error messages (failling hardware generally shows up here).

[    7.616000] sd 2:0:0:0: [sda] 156301488 512-byte hardware sectors (80026 MB)

[   16.076000] iwl3945: Tunable channels: 11 802.11bg, 13 802.11a channels

Want to see how much memory is actually being detected? (Windows and many BIOS’s round these numbers)

cat /proc/meminfo

Want to know a bunch of information about the CPU in the machine? Then cpuinfo is for you.

cat /proc/cpuinfo

Run Levels

In Linux, you generally have run levels that range from 0-6.

0: Halt (shutdown) the system
1: Single user mode (major upgrades, maintenance, etc.)
2: Basic multi user mode
3: Full multi user mode
4: Unused (custom)
5: Multi user mode with GUI
6: Reboot

0,1 and 6 are always the same, but different distros do different things with the other run levels (for example, Debian-based systems use run level 2 for GUI and full multi-user mode)

You can see what services start at what run level by looking in the directory /etc/rc#.d where # is the run level number.

The run level number can be found in /etc/inittab (id:2:initdefault: for example)
If you were to look in /etc/rc2.d, you would see files that look like:

S99program

These are usually symbolic links to files in /etc/init.d (so a change to /etc/init.d/program would change the programs script for every run level).

Start-up scripts in Linux follow the form “start-stop” (at minimum). Many have “start-stop-restart-reload-check” or possible more.

A basic start-stop script would look like this:

#!/bin/bash
case $1 in
start)
program
;;
stop)
program
;;
esac

Don’t forget

chmod +x script

This is useful to know, especially if you are dealing with a machine that may need specific commands to be run when booting or shutting down in order to function properly (for example, in the radio station we need the client machines to run dhclient at S99 in order to obtain an IP address).

These scripts are not all run at once (by default). S##program where ## is the priority of the script.

S99 will run last, while S10 will run before most other things.

Obtain free Cisco IOS upgrades

0. Determine who purchased the device. You will need to send an email from their CCO registered account. This does not mean it needs an active contract.
1. Log onto the device and capture all of the output of “show version”
2. Go to http://tools.cisco.com/security/center/selectIOSVersion.x  and select the “B” option to use the “show version” output
3. Choose to view all security vulnerabilties
4. Send an email to [email protected] with
  • ​The output of “show version” in the body of the e-mail
  • Serial number of the device in the body of the e-mail (yes, even though it’s in show ver)
  • A list of all vulnerabilities for the selected IOS from cisco’s website in the body of the e-mail (just copy and paste the links)
  • Request a non-vulnerable IOS version

 

​5. Wait and they should send you a link to download the IOS.

Cisco wireless access point and Windows 2008 RADIUS EAP Authentication

Configure Windows server for RADIUS
1. Install NPS and CA authority roles if you have not already
2. Go to Computer Management. Roles – Network Policy and Access –  NPS (Local) – RADIUS Clients
3. Create new RADIUS client

 

  • ​Friendly name: Name of AP (Example: corp-ap-1141-il)
  • IP Address: IP of AP
  • Shared Secret – Manual (Generate a random 12+ digit key with no special chars)
  • Under “Advanced” tab, Vendor name: Cisco and check “RADIUS client is NAP capable”

4. Under NPS – Policies –  Network Policies create a new Policy called ‘Cisco AP Radius’

  • ​Condition Tab: Windows Groups (Domain Users)
  • Constraints Tab
    • Auth Methods: Add all three auth methods. Check MS-CHAPv2, MS-CHAP, CHAP and PAP/SPAP
    • NAS Port Type: Select Wireless 802.11 under Common 802.1x types and “Wireless Other” under “Others”
  • Settings Tab
    • Standard: add Service-Type Login

​5. When done, move the Cisco AP Radius policy to the #1 position

 
​Configure Cisco AP for RADIUS

 
1. Enter in RADIUS group information
aaa new-model
aaa group server radius rad_eap
     server 10.0.0.3 auth-port 1812 acct-port 1813
aaa authentication login eap_methods group rad_eap
aaa session-id common
radius-server host 10.0.0.3 auth-port 1812 acct-port 1813 key KEYYOUGENERATEDEARILER
dot11 ssid CompanyWifi
   no authentication open
   no wpa-psk ascii
   authentication open eap eap_methods
   authentication network-eap eap_methods

2. Try to connect with a client computer. Debug on AP with: debug radius authentication​