Helpful software

Again, not coding stuff (I’ve been sick so I’ve been sleeping a little more than normal, I think..), but a couple different somewhat related programs I’ve found helpful.

Virtual Box: my Linux install on my USB keeps having errors for one reason or another (literally, I’ve reinstalled it 5-6 times), and it has stopped working from the CD as well. So this allows you to install other operating systems on a virtual computer.

VirtuaWin: one of the things I did like about Linux was the multiple desktops – this allows you to have that on Windows. So if you’re coding one project, you can have all the windows associated with that open on one desktop, have games and stuff open on another, some other project open on another, etc… I have it set up with 4 desktops (most of the time I don’t need more than 2 or 3), but you can have a whole bunch.

States Dropdown

No learning here, just something that I seem to end up copy-pasting a lot, so I’ll be able to find it easily here.. (And it’d be easy to do a find-replace all of ‘asp:ListItem’ to ‘option’ if it’s going to be used in an html page rather than an asp/aspx page. Also, the required field validator would need to be taken out; that’s only if you want it to be required for a state to be selected, before the form can be submitted.)

<asp:RequiredFieldValidator ControlToValidate="ddState" ID="Neko" runat="server" ErrorMessage="RequiredFieldValidator" Text="*" SetFocusOnError="true" />
State:
<asp:DropDownList ID="ddState" runat="server">
  <asp:ListItem Selected="True" value="">Choose A State</asp:ListItem>
  <asp:ListItem value="AL">Alabama</asp:ListItem>
  <asp:ListItem value="AK">Alaska</asp:ListItem>
  <asp:ListItem value="AZ">Arizona</asp:ListItem>
  <asp:ListItem value="AR">Arkansas</asp:ListItem>
  <asp:ListItem value="CA">California</asp:ListItem>
  <asp:ListItem value="CO">Colorado</asp:ListItem>
  <asp:ListItem value="CT">Connecticut</asp:ListItem>
  <asp:ListItem value="DE">Delaware</asp:ListItem>
  <asp:ListItem value="DC">District of Columbia</asp:ListItem>
  <asp:ListItem value="FL">Florida</asp:ListItem>
  <asp:ListItem value="GA">Georgia</asp:ListItem>
  <asp:ListItem value="HI">Hawaii</asp:ListItem>
  <asp:ListItem value="ID">Idaho</asp:ListItem>
  <asp:ListItem value="IL">Illinois</asp:ListItem>
  <asp:ListItem value="IN">Indiana</asp:ListItem>
  <asp:ListItem value="IA">Iowa</asp:ListItem>
  <asp:ListItem value="KS">Kansas</asp:ListItem>
  <asp:ListItem value="KY">Kentucky</asp:ListItem>
  <asp:ListItem value="LA">Lousiana</asp:ListItem>
  <asp:ListItem value="ME">Maine</asp:ListItem>
  <asp:ListItem value="MD">Maryland</asp:ListItem>
  <asp:ListItem value="MA">Massachusetts</asp:ListItem>
  <asp:ListItem value="MI">Michigan</asp:ListItem>
  <asp:ListItem value="MN">Minnesota</asp:ListItem>
  <asp:ListItem value="MS">Mississippi</asp:ListItem>
  <asp:ListItem value="MO">Missouri</asp:ListItem>
  <asp:ListItem value="MT">Montana</asp:ListItem>
  <asp:ListItem value="NE">Nebraska</asp:ListItem>
  <asp:ListItem value="NV">Nevada</asp:ListItem>
  <asp:ListItem value="NH">New Hampshire</asp:ListItem>
  <asp:ListItem value="NJ">New Jersey</asp:ListItem>
  <asp:ListItem value="NM">New Mexico</asp:ListItem>
  <asp:ListItem value="NY">New York</asp:ListItem>
  <asp:ListItem value="NC">North Carolina</asp:ListItem>
  <asp:ListItem value="ND">North Dakota</asp:ListItem>
  <asp:ListItem value="OH">Ohio</asp:ListItem>
  <asp:ListItem value="OK">Oklahoma</asp:ListItem>
  <asp:ListItem value="OR">Oregon</asp:ListItem>
  <asp:ListItem value="PA">Pennsylvania</asp:ListItem>
  <asp:ListItem value="RI">Rhode Island</asp:ListItem>
  <asp:ListItem value="SC">South Carolina</asp:ListItem>
  <asp:ListItem value="SD">South Dakota</asp:ListItem>
  <asp:ListItem value="TN">Tennessee</asp:ListItem>
  <asp:ListItem value="TX">Texas</asp:ListItem>
  <asp:ListItem value="UT">Utah</asp:ListItem>
  <asp:ListItem value="VT">Vermont</asp:ListItem>
  <asp:ListItem value="VA">Virginia</asp:ListItem>
  <asp:ListItem value="WA">Washington</asp:ListItem>
  <asp:ListItem value="WV">West Virginia</asp:ListItem>
  <asp:ListItem value="WI">Wisconsin</asp:ListItem>
  <asp:ListItem value="WY">Wyoming</asp:ListItem>
</asp:DropDownList>


Find if a number is a power of two: Part 2

My 1GB USB has 0 bytes left so Linux cannot boot from it; I have to reinstall Linux from the Live CD again… yaaay… </sarcasm> Anyways, so I looked up the solution to how to find using only bitwise operators, if a number is a power of two. This site led me to another site with 10 different ways to check if an integer is a power of two; the one I need is a slight modification of the 9th way:

int isPowerOfTwo (unsigned int x) {
  return ((x != 0) && !(x & (x - 1)));
}


I couldn’t use exactly this, because of only being allowed these operators: & | ^ ! + >> << ~. So…here (I’ve broken the parts into separate variables so it doesn’t break onto multiple lines for one line of code, and also so I can use a few less parentheses to make sure the operations happen in the right order):

int isPowerOfTwo (int x) {
  int a = !( (x>>31) & 1 );
  int b = !(!x);
  int c = !( x & ( x + ((((((FF<<8)+FF)<<8)+FF)<<8)+FF) ) );
  return ( a & b & c );
}

a will return 0 if x is less than 0.
b will return 0 if x is 0. (Using ! twice makes 0 return 0 and anything else return 1.)
c’s explanation I just pasted from the website…since it sums it up nicely.
*Note: ( x + ((((((FF<<8)+FF)<<8)+FF)<<8)+FF) ) is using two’s complement to subtract one from x since we couldn’t use -.

---

!(x & (x-1)) is true when x is a power of two and false when x is not. Let’s see why.

Let n be the position of the leftmost 1 bit if x. If x is a power of two, its lone 1 bit is in position n. This means x – 1 has a 0 in position n. To see why, recall how binary subtraction works. When subtracting 1 from x, the borrow propagates all the way to position n; bit n becomes 0 and all lower bits become 1. Now, since x has no 1 bits in common with x – 1, x & (x – 1) is 0, and !(x & (x – 1)) is true.

Here are some examples (I’ll use 8-bit unsigned integers to keep things manageable):

Decrement and Compare, when x is a power of two:
x / x – 1 / x & (x – 1)
00000001 00000000 00000000
00000100 00000011 00000000
00010000 00001111 00000000

If x is not a power of two, x – 1 has a 1 in position n. This is because the borrow will not propagate to position n. Subtraction borrows from the lowest 1 bit, which by virtue of x not being a power of two, is before position n. The lowest 1 bit is like a firewall that prevents the borrow from reaching position n. Since x and x – 1 have at least one 1 bit in common — at position n — x & (x – 1) is non-zero, and !(x & (x – 1)) is false.

Here are some examples:
Decrement and Compare, when x is a NOT power of two:
x / x – 1 / x & (x – 1)
00000011 00000010 00000010
00000110 00000101 00000100
00001011 00001010 00001010
00011100 00011011 00011000

Find if a number is a power of two

I took a midterm today, for one of my programming classes, and realized what I could have given as at least a partial answer to one of the questions a few minutes too late. And so, I have a need to write it down in full somewhere.

The question was, how to find if a number is a power of two, using only bitwise operators, and no more than 40; and without any constants larger than 8 bits. (We could use & | ^ ! + >> << ~) *Note: negative numbers were considered excluded, and so should return 0. Only positive numbers that were powers of two should return 1.

isPowerOfTwo(int x) {
  int y = 31 - (x >> 1);
  return ( ((x<<y) >> 31) & 1);
}
I am still not sure exactly where to go with this. Bummer, because earlier I thought it would be the solution, but only when I typed it out now did I see the problem with it… Instead, it seems to return if the bit at the specified power of two is a 0 or a 1? I’m not sure exactly, and I’m supposed to be writing an essay, not writing code, so I can’t take the time to figure out what it does or the correct solution right now. It is bugging me…

*Random other side thought: I had to include the “CPP” in the C++ category, because apparently WordPress does not recognize a difference between “C++” and “C” as the category name; and it thought I was trying to add the same category twice. It probably normally doesn’t make a difference, but there are instances where code is not compatible between C and C++, and well…that’s not even getting into C#.

Happy birthday Peeky :)

Just want to say happy birthday to my little guinea pig…

She’s not physically with us any more, but I keep her spirit with me. :)

GDB Debugger

I’m not really sure where this belongs. GDB is a Linux debugger but I’m using it to step through assembly code of a program I don’t have the source code for, as a homework assignment, to find secret phrases hidden in the code… (This is an edited-for-nice-formatting copy-paste of GDB-commands-x86-64.txt because it’s been extremely helpful, and in case it ever gets taken down.)

---

Summary of GDB commands for x86-64 Systems
Command -------- Effect
Starting and stopping
quit ---------- Exit gdb
run ----------- Run your program
run [args] ---- Run your program using the specific command-line arguments

Breakpoints
break sum --------- Set breakpoint at the entry to function sum
break *0x80483c3 -- Set breakpoint at address 0x80483c3
delete 1 ---------- Delete breakpoint 1 (gdb numbers each breakpoint you create)
delete ------------ Delete all breakpoints
until 3 ----------- Continue executing until the program hits breakpoint 3

Execution
stepi ------- Execute one instruction
stepi 4 ----- Execute four instructions
nexti ------- Like stepi, but proceed proceed through function calls without stopping
continue ---- Resume execution until the next breakpoint
finish ------ Resume execution until current function returns

Examining code
disas ------------ Disassemble current function
disas sum -------- Disassemble function sum
disas 0x80483b7 -- Disassemble function around 0x80483b7
disas 0x80483b7 0x80483c7 - Disassemble code within specified address range
-
print /x $rip ---- Print program counter in hex
print /d $rip ---- Print program counter in decimal
print /t $rip ---- Print program counter in binary
-
call sum(1, 2) --- Call sum(1,2) and print return value

Examining data
print /d $rax -------------- Print contents of %rax in decimal
print /x $rax -------------- Print contents of %rax in hex
print /t $rax -------------- Print contents of %rax in binary
print 0x100 ---------------- Print decimal representation of 0x100
print /x 555 --------------- Print hex representation of 555
print /x ($rsp+8) ---------- Print (contents of %rsp) + 8 in hex
print *(int *) 0xbffff890 -- Print integer at address 0xbffff890
print *(int *) ($rsp+8) ---- Print integer at address %rsp + 8
print (char *) 0xbfff890 --- Examine a string stored at 0xbffff890
print /d (int)$rax --------- Print contents of %rax in decimal after sign-extending lower 32-bits.**You need this to print 32-bit, negative numbers stored in the lower 32 bits of %rax. For example, if the lower 32-bits of %rax store 0xffffffff, you will see:
(gdb) print $rax
$1 = 4294967295
(gdb) print (int)$rax
$2 = -1
(gdb)

Examining Data (continued)
x/w 0xbffff890 ------- Examine (4-byte) word starting at address 0xbffff890
x/w $rsp ------------- Examine (4-byte) word starting at address in $rsp
x/wd $rsp ------------ Examine (4-byte) word starting at address in $rsp. Print in decimal
x/2w $rsp ------------ Examine two (4-byte) words starting at address in $rsp
x/2wd $rsp ----------- Examine two (4-byte) words starting at address in $rsp. Print in decimal
x/g $rsp ------------- Examine (8-byte) word starting at address in $rsp.
x/gd $rsp ------------ Examine (8-byte) word starting at address in $rsp. Print in decimal
x/a $rsp ------------- Examine address in $rsp. Print as offset from previous global symbol.
-
x/s 0xbffff890 ------- Examine a string stored at 0xbffff890
-
x/20b sum ------------ Examine first 20 opcode bytes of function sum
x/10i sum ------------ Examine first 10 instructions of function sum
Note: the format string for the `x’ command has the general form x/[NUM][SIZE][FORMAT] where:
* NUM = number of objects to display
* SIZE = size of each object (b=byte, h=half-word, w=word, g=giant (quad-word))
* FORMAT = how to display each object (d=decimal, x=hex, o=octal, etc.)
If you don’t specify SIZE or FORMAT, either a default value, or the last value you specified in a previous `print’ or `x’ command is used.

Useful information
info frame ---------- Print available information about current stack frame
info registers ------ Print values in all registers
display /FMT EXPR --- Print expression EXPR using format FMT ever time GDB stops
undisplay ----------- Turn off display mode
help ---------------- Get information about gdb

Substring

$kami="I am awesome."
$neko=${kami:0:4}
# $neko == "I am"

While loop

Self explanatory, I think.
while condition
do
  # statements
done

To have a “do while” loop:
while True
do
  # statements
  if [ condition ]
    break
done

Case statement (esac)

Everything between 0) and the first ;; gets run if variable==0 (so if there were no ;;, it would continue running the statements after 1), similar to C++ if break is not there). The default condition if none of the others match is *).

case $variable in
  0)
      # statements
  ;;
  1)
      # statements
  ;;
  *)
      # statements
  ;;
esac

Debugging

This goes in the script file.

set -x