FB n00b: Tutorial 8

Note: This tutorial is for absolute beginners. If you aren't an absolute beginner and you dislike the tutorial, that's too bad. If you are an absolute beginner and there's something you don't understand, read through the tutorial a second time. If you STILL have difficulties, e-mail me (TheMysteriousStrangerFromMars@yahoo.com) and I'll try to help you out. I do assume you at least have a decent knowledge of how to use your computer - if not, there's not much I can do for you. By the way, you'll need FreeBasic to use this tutorial - you download that at freebasic.net, so be sure to download and install it before doing this tutorial. Now start reading!

How your computer really works

Or, a round-about introduction to pointers

Throughout this series I've tried to help you see what's going on inside your computer, to understand how things really work. Obviously you can't remove all levels of abstraction unless you have a working understanding of microelectronics and hardware design (I don't, and you probably don't either), but I try to explain how it all fits together from a programmers perspective, because to me it's important.

The lengths to which I go may seem like overkill to some, but it's well worth it. The things I'll teach you should, in my opinion, be taught to every

The brain of your computer, of course, is the processor or CPU. This is an extremely complicated (and getting more so) chip mounted on the motherboard. A CPU takes binary data and interprets these numbers as commands. Basically, it takes numbers out of memory which may instruct it to perform operations on or with other numbers in memory (of course, the numbers which are machine language instructions may also do other things). In the early days, there were many different CPUs and each had its own machine language - that is, each interpreted the numbers differently. Now, however, most CPUs used today are compatible at least in some basic way with the original 8086 chip by Intel. There are other CPUs, but they are mostly for special purposes (such as supercomputers). Any PC you buy (and as of now that includes Macs as well, though before they used different chips) has an Intel or Intel-compatible (such as AMD) processor chip. At the low level, this makes things much easier for the programmer, since his programs can be used on the majority of systems. At higher levels, such as the level we're at, it doesn't really matter, since FreeBasic only works on 80x86-compatible systems, and in fact only supports three operating systems (DOS, Windows, and Linux).

The CPU connects via the motherboard to the "bus." This puts all the data in and out between the CPU and everything else - your memory and external devices such as your hard drive, CD drive, mouse, keyboard, printer, scanner, USB ports, networking card, sound card, video card, and anything else in or connected to your computer. To access data via the bus, the bus has to know which data is being accessed. For every single thing accessible via the bus, there is a number - known as the address - that is sent from the CPU to the bus. After the address is sent, the CPU tells the bus whether it wants to read from or write to that address. If reading, the bus sends the value from that address to the CPU. If writing, the CPU sends the number it wants to write to the bus.

The CPU has various internal registers for making calculations. Some may be used by the programmer (eax, ebx, edx, ecx, for example, are used in assembly) while others are only used internally. Thus, to increment a number by 1 (in assembly this is done with "inc something") the CPU sends the address to the bus, tells the bus to read the number, reads the number from the bus and increments it (using a complex logic circuit known as an adder), and puts the number back on the bus along with the same address and an instruction to write this time. Fortunately, even in assembly language you don't have to worry about all that - the CPU does it for you.

Access to other devices than memory, like hard drives, is done in exactly the same way - except that the address sent to the bus is in a special range of numbers which are never used to access memory. In fact, to access any device other than memory an entirely different set of instructions are used than those used to access memory (IN and OUT are the main mnemonics used for this in assembly language), so you are abstracted from the confusing fact that it's actually all done in the exact same way.

Modern CPUs use what is known as protection, meaning that except for the operating system itself, most programs you run may not directly access the devices or even any part of memory except the memory assigned to it by the operating system (incidentally, protection is optional, but all modern operating systems support it). In this way, the programs are protected from each other and the operating system is protected from the programs (making it more difficult to write viruses, but not quite impossible since every system has bugs in it) - this can be thought of similarly to scope control (for example the fact that you can create variables inside Subs or Functions that do not even exist so far as the rest of the program is concerned), but at a much lower level.

The CPU can only execute code that is in memory - it can't, for example, run a program directly off the hard drive (which would be very slow anyways, since memory is much faster than any disk). So how does it execute your operating system, which is normally in RAM memory (which is erased whenever your computer is off)? Easy: ROM. ROM, or Read-Only Memory (RAM stands for Random-Access Memory) contains the code necessary to load the operating system off the disk and into memory. The code that does this is known as the Basic Input/Output System or BIOS. This is because it does very little, it's very very basic (though modern BIOSes have a lot of extra functions to aid the OS with Plug 'N Play). The BIOS is the first thing the CPU starts to execute, and all it does is check to make sure the system is OK and then attempts to load a small portion off your disks (usually it checks the disks in a certain order, and the first one that has a magical number, &h55AA, is used) which it will then transfer control to. This small bit of code (usually only 512 bytes, which is hard to fit much meaningful code into) is known as the bootstrap or the bootloader, and it must load the rest of your operating system into memory.

The operating system usually starts in "real" mode, meaning protection is not enabled yet - if it were, the CPU wouldn't know the difference between the OS and any other program! The OS must enable protection, so the CPU allows it to have the priveleges but the OS controls everything so the other applications are protected.

In the old day, memory addresses were a 20-bit number (they actually used the form segment:address, where segment and address were 16 bits and segment was multiplied by a number before being added to the address to get the true address in memory); in protected mode, however, an address is often not at all based on the actual address in memory. It is mapped to a physical address by the CPU automatically, and the operating system of course is in control of just how this mapping is done. It becomes even more complicated when paging is introduced, which most modern operating systems support and which I won't explain here. All this is done to give each program the illusion that it occupies memory and the CPU all on its own - that no other program is running with it, and that it gets all the resources of the computer to itself. This of course is not true, but the OS sets everything up very nicely so in effect every program gets access to the full resources of the computer, though in fact they are shared with many, many processes.

Now, back to programming, where fortunately all of this is hidden from us.

Pointers

There are some instances in computer science where it is useful to deal not directly with variables, but actually with the location of variables. For example, for memory efficiency, we might not declare all the variables we'll need, but may instead create or destroy variables as we need them or don't need them. For example, we may need to load some data out of a file and into memory, without knowing ahead of time how many bytes the file contains. Aside from using a variable-sized array (which, for one thing, cannot be used within UDTs), our best chance is to allocate or set aside some memory for such purposes while the program is running - and long after we've already compiled the program, meaning we can't just declare such variables using Dim.

Enter the pointer. This is an extremely important concept in programming, so pay attention! A pointer is a special kind of variable which holds the address of a variable or a bunch of variables. When working with pointers, it is important to remember the difference between the pointer itself and what it points to. You can access or modify either one, but obviously if you access the wrong one your program won't work properly.

Also, if we want to be able to treat a pointer as an array, we need to have different kinds of pointers. For example, an integer takes up four bytes, so if you add one to an integer pointer, for will actually be added. Pointer arithemetic may seem a little bit complicated at first, but if you think about it the reason for this is actually to make things easier on you.

With all this in mind, let's see a simple example of using a pointer:

  'Create an integer and a pointer that points to it
  Dim As Integer myInteger = 3
  Dim As Integer Ptr myIntPtr = @myInteger

  'Look at the integer and what the pointer points to...
  'They're the same!
  Print myInteger
  Print *myIntPtr

  'What will modifying the value pointed to by the pointer do?
  *myIntPtr += 1

  'Since they're still the same, we can see that the pointer really
  'does point to the same address the integer is stored at!
  Print *myIntPtr
  Print myInteger

  Sleep

Basically, the @ gives the address of a variable - including the pointer itself:

  @myIntPtr

  myIntPtr

  *myIntPtr

Now, since we set our pointer to the address of myInteger, the * operator allows us to access the contents of myInteger - though of course at any time we could make the pointer point to something else, and then * would access whatever the pointer points to then.

In general, you must not use a pointer that doesn't point to anything. Generally pointers not being used are set to 0; this allows you to check if a pointer is valid or not (since 0 pointers are never valid), but it won't prevent you from using the pointer.

Memory Buffers

Now, it's one thing to use a pointer to simply point to a variable already created, and there are some practical uses for that, but even more important is the possibility of allocating, reallocating, and deallocating areas in memory (sometimes referred to as buffers) while the program is running.

Imagine a spreadsheet program. Each cell holds a string. When we start the program, there is only one cell - but the user may want to expand it to any size, or once expanded, later contract it if it's too large. Obviously, since you don't know how many cells to allocate ahead of time, your best bet is a dynamic array... oops! Those won't work with strings, unless you use statically sized strings.

Another option is to simply allocate a lot of memory (declare a very large static array, such as 65536x65536). Unfotunately, there would be a lot of memory wasted this way, since no user is likely to use that much, yet if you allocate a more realistic amount - who knows but that the user just happens to need more?

With pointers, you don't have these problems. You can use strings and UDTs, and you can size and resize pointers as you need to. I'll show you an example with integers; you can easily do it with any other variable type.

First, you create a pointer but you don't assign it to the address of any variable. Instead, you use the function Allocate(). Allocate() needs to know how many bytes to allocate, and it returns a pointer to the first byte in a buffer of that size. It's important to remeber that the amount allocated is always in bytes - so for example, if you want to allocate 3 integers, you must pass 3*4 = 12 to Allocate() instead of just 3.

Actually, as time goes on, variable sizes may change. On 64-bit machines, for example, integers may be 8 bytes instead of 4. Though FreeBasic doesn't support 64-bit compiling yet, it may in the future, so to make sure you're always compatible you should use the SizeOf() function to figure out what to multiply by. For example, to create a pointer myIntPtr and point it to a buffer of 3 integers:

  Dim As Integer myIntPtr = Allocate(3 * SizeOf(Integer))

Of course, you don't have to allocate the space right away; you can also declare the variable once and allocate the space later as well:

  Dim As Integer myIntPtr

  'Insert other code here

  myIntPtr = Allocate(3 * SizeOf(Integer))

Once you've allocated it, you may at any time ReAllocate() it to a different size. This allows you to change the size of the buffer, without changing the current contents (the new things you add must be initialized, of course, or you can't count on their contents to be a specific value - they could be anything). ReAllocate() needs the original pointer and, once again, the number of bytes to allocate. If nothing else has been allocated, it may be possible to add more to the end of the buffer. Usually, however, ReAllocate() may end up moving the contents of the old buffer to the new larger buffer, and DeAllocating the old one. Of course, you can also ReAllocate() your buffer to a lower size.

  myIntPtr = ReAllocate (myIntPtr, 5*SizeOf(Integer))

Finally, you should always DeAllocate() when you're done - at the end of the program, or even at the end of a procedure if it isn't used by the main program (sometimes a function may allocate some memory and return the pointer, in which case of course the caller must deallocate and not the function itself) - or if you're done using that area of memory but need the same pointer to point to something else (otherwise you'll be wasting memory, especially if you decide to reuse the pointer since there's no way to find what it originally pointed to before).

To DeAllocate, your only argument is the pointer itself - obviously since you're just destroying the memory buffer, you don't need to specify any size argument:

  DeAllocate(myIntPtr)

All this is really great, and there's just one thing to be careful of (other than the obvious - not losing track of your pointers, deallocating when you're done, etc.): allocating and reallocating memory can slow you down. It's a necessary procedure in many cases, but generally you shouldn't do any allocating or reallocating in within a loop. When possible, do all the allocating you need to do before you enter a loop.

Pointer Arrays

So how about using pointers as arrays? Earlier we allocated space for three integers, but using the normal * operator we can only access the first of the three. Even when we reallocate to five integers - we can still only access the first one!

There is another syntax used, and it's very much like the syntax for the array except that you use [] instead of (). An example follows:

  Dim As Integer Ptr myList

  myList = Allocate(10*SizeOf(Integer))

  For i As Integer = 0 to 9
    myList[i] = i
  Next i

  '...

  For i As Integer = 0 to 9
    Print myList[i]
  Next i

  Sleep

There is an alternate way of doing this - there always is, of course:

  'The following two lines are identical
  *(myList + i)
  myList[i]

Yet another method is to add 1 to the pointer each time. Because of pointer arithmetic, this actually adds SizeOf(Integer) (or whatever type of variable you use), so it works properly. Since this modifies the pointer, it usually isn't used except in procedures which use a pointer that has been passed ByVal and is only needed once - for example:

  Sub mySub (myIntPtr As Integer Ptr, numInts As Integer)
    While numInts
      myIntPtr = myIntPtr + 1
      numInts = numInts - 1
      Print *myIntPtr
    Wend
  End Sub

Incidentally, *myIntPtr and myIntPtr[0] are exactly the same thing - and the same is of course true for any type.

There is yet another special pointer syntax, this one used in relation to UDTs - or specifically, accessing the members of a UDT pointer:

  'Define a type
  Type myType
    a As Integer = 3
  End Type

  'Declare a variable of that type and create a pointer that points to it
  Dim As myType q
  Dim As myType Ptr p = @q

  Print q.a

  'The following three statements are identical:
  Print p->a
  Print (*p).a
  Print p[0].a

  Sleep

Wrapping up

Pointers are important when working with UDTs, and especially objects as you'll see. They are especially used with certain data structures: trees, stacks, queues, linked- and double-linked lists, and others, which you'll discover. Any time you load data off the disk and into memory - for example, graphics for a game - you need a pointer to keep track of where in memory it's stored.

Now, however, we begin to hit the chicken and egg problem - to understand the significance of the pointer you must be introduced to yet other concepts, but in order to understand those concepts you must understand the pointer itself! Now that you've seen the pointer, we'll be able to explore some other topics. This chapter, however, is finished.

The ninth chapter will cover file I/O in FreeBasic, something it's high time we covered.

The ninth tutorial is here