text:
Modern Greek/Lesson 03.2

= Lesson 3.2: Gender of Nouns =

In Lesson 3.1 we saw that in modern Greek there are three genders, masculine, feminine, and neuter. Every noun has a gender. For some nouns this is obvious (like actor and actress in English), but for some it is less obvious. The endings of nouns often help to identify the gender, though there are many exceptions. Later we will see that adjectives have to agree with the gender of the nouns, as well as some of the question words. For now though, we introduce the definite article for each gender, and some common nouns.

Masculine nouns
Σκύλος, dog, is a masculine noun. Note the different forms of the definite article.

''NOTE: Previously it was possible to drop the "ν" at the end of τον under certain circumstances. In Modern Greek (as of very recently) this is no longer true, and the masculine definite article should always be τον, though you will find lots of counter-examples still.''

The ending -ος is the most common one for masculine nouns, and σκύλος demonstrates their regular pattern. Another noun in -oς is άνθρωπος (e.g. anthropology), human/man

Although -ος is by far the most common ending for masculine nouns, there are others, including -ας as in πατέρας, father, and -ης, as in ναύτης, sailor..

For example: Ο σκύλος δαγκώνει τον πατέρα. The dog bites the father.

Feminine nouns
The noun Η ώρα (the hour, the time) is shown below:

NOTE: With the feminine accusative the final ν of την can be dropped under certain circumstances, but should be retained if the noun starts with a vowel, or κ, π, τ χ, θ, ξ φ, ψ, σ

NOTE: The presence of the additional sigma is because I'm going TO the sea, and σε + accusitive gets abbreviated, this will be explained more fully in TBC and serves only as a common example for now.

Neuter nouns
Το παιδί (the child) is an example of a neuter noun.

Below is an example of a sentence using the noun.

Summary Table
A summary table of the definitive article. Note that the "ν" is kept only if the following word starts with κ,π,τ,ψ,ξ or a vowel.

Summary

 * We have seen TBC.

Exercises
Now try the exercises here.

title: Modern Greek/Lesson 03.2


text:
Modern Greek/Lesson 03.3

= Lesson 3.3: Summary of Pronouns =

Pronouns are used to replace nouns, e.g. John goes becomes He goes.

Pronouns have cases, number and gender just as regular nouns do.

A summary of all the pronouns is given in the table below.

NOTE: For the third person they are masc., fem., neuter within one box (in that order).

 * Though no-one uses this, αυτούς, is used instead.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Modern Greek/Lesson 03.3


text:
User talk:Eesteve~enwikibooks

Hello, and welcome to wikibooks! I see that you rearranged one of my outlines on my user page. I always welcome all the help that I can get on my projects, so thank you very much for helping out. If you need anything, don't hesitate to ask, and if you would like to help more on some of my projects (or on any projects here for that matter) feel free to dive right in. Thank you again, and have fun here! --Whiteknight (talk) (projects) 14:40, 25 May 2006 (UTC)

Your account will be renamed
Hello,

The developer team at Wikimedia is making some changes to how accounts work, as part of our on-going efforts to provide new and better tools for our users like cross-wiki notifications. These changes will mean you have the same account name everywhere. This will let us give you new features that will help you edit and discuss better, and allow more flexible user permissions for tools. One of the side-effects of this is that user accounts will now have to be unique across all 900 Wikimedia wikis. See the announcement for more information.

Unfortunately, your account clashes with another account also called Eesteve. To make sure that both of you can use all Wikimedia projects in future, we have reserved the name Eesteve~enwikibooks that only you will have. If you like it, you don't have to do anything. If you do not like it, you can pick out a different name.

Your account will still work as before, and you will be credited for all your edits made so far, but you will have to use the new account name when you log in.

Sorry for the inconvenience.

Yours, Keegan Peterzell Community Liaison, Wikimedia Foundation 23:07, 17 March 2015 (UTC)

Renamed
 This account has been renamed as part of single-user login finalisation. If you own this account you can |log in using your previous username and password for more information. If you do not like this account's new name, you can choose your own using this form after logging in: . -- Keegan (WMF) (talk) 04:55, 19 April 2015 (UTC)

title: User talk:Eesteve~enwikibooks


text:
Video Game Design/Programming/Framework/2D vs 3D/3D Engine

3D Engine
If the game requires a 3D environment, it signifies that it will use a 3D view that is characterized by the use of polygon based graphics. Polygons are flat shapes and in a low count (low resolution polygon scenes) graphics are often angular.

A good 3D engine should run at a decent speed, no matter what the size of the full world is; speed should be relative to the amount of detail that is actually visible. It would of course be even better if the speed would only depend on the number of pixels you want to draw, but since apparently no one has found an algorithm that does that, we can not do more that attempt to improve upon past work.

This section will attempt to describe the components in the architecture of a 3D Engine. A 3D Engine encompasses a lot of concepts. We will do our best to cover other systems that use 3D engines (such as programs like auto cad, blender, medical programs, etc) but we will focus in specific in 3D engines for games.

Game engines are a very broad complex topic. They have their own architectures and approaches directed toward the features that are necessary to be in a particular game or game type. The way one engine works is not necessarily how all engines work, or even most, that is to say each is a unique creation.

The 3D nature of the world will require that most of the concept art after approval to be scanned and modeled onto planes in a 3D modeling application such as Maya or 3DsMax.

Some popular 3D graphics engines: Crystal Space, Irrlicht, Ogre3D

Examples of 3D modeling and animation: AutoDesk(formerly Alias) Maya, 3dbuzz, AutoDesk 3dsMax, Blender, TrueSpace (now free)

Portals
Basically, a portal based engine permits the 'spatially indexing' of large datasets that usually make up the virtual world: in other words, it can be a simple technique to avoid having to display all that data in every frame and instead only draw what is relevant even permitting to save fast memory requirements.

A basic portal engine relies on a data set that represents the world. The 'world' is subdivided in areas, that I call 'sectors'. Sectors are connected through 'portals', hence the name 'Portal Engine'. A portal-based engine world can be thought of as a variation of a boundary representation (or B-rep) data structure that is very much special-cased to the properties of a gaming world. The rendering process starts in the sector that the camera is in. It draws the polygons in the current sector, and when a portal is encountered, the adjacent sector is entered, and the polygons in that sector are processed. This would of course still draw every polygon in the world, assuming that all sectors are somehow connected. But, not every portal is visible. And if a portal is not visible, the sector that it links to doesn't have to be drawn. That's logical: A room is only visible if there's a line of sight from the camera to that room, that is not obscured by a wall.

So now we have what we want: If a portal is invisible, tracing stops right there. If there's a huge part of the world behind that portal, that part is never processed. The number of polygons that are actually processed is thus almost exactly equal to the number of visible polygons, plus the inserted portal polygons.

By now it should also be clear where portals should be inserted in a world: Good spots for portals are doors, corridors, windows and so on. That also makes clear why portal engines suck at outdoor scenes: It's virtually impossible to pick good spots for portals there, and each sector can 'see' virtually every other sector in the world. Portal rendering can be perfectly combined with outdoor engines though: If you render your landscape with another type of engine, you could place portals in entrances of caves, buildings and so on. When the 'normal' renderer encounters a portal, you could simply switch to portal rendering for everything behind that portal. That way, a portal engine can even be nice for a 'space-sim'...

Your own 3D Engine
Sometimes the available offering of 3D engines will not match your game's requirements, the features or licensing. 3D game engines are huge software projects. A single person can indeed write one, but it is not an overnight process. It will probably result in having more than a few megabytes of source code. If one is not to committed to finish it, the attempt will fail and even put the whole game project at risk.

Before start coding the engine some effort is required in planing, just like the game itself, so to determine what will one do with engine or what can be implemented. Most often, the creation 3D engines arises from the requirements of specific games, but they can be seen a product in themselves. Do not expect to write a full engine at the first try, if one must be built and there is a lack of time or knowledge, get the right people to do it or direct the effort toward a smaller game project that has an equal small requirements list for the engine.

Do not just jump in and start coding an engine, as errors will be made and create the need to re-write huge portions of the engine multiple times to add effects and control later. A little forethought into engine design will save headaches and time.

The list of features in a 3D engine can include curved surfaces, dynamic lighting, volumetric fog, mirrors and portals, skyboxes, vertex shaders, particle systems, static mesh models and animated mesh models. If one has a good idea of how all these things work, and the technical capability to implement them, one may probably start putting them together into an his own engine.

In this section we will discusses the elements normally present in a 3D engine. These essentially includes the tools, console, systems, renderer, engine core, game interface and the game itself.

Let's take a look at the basic components, using example of a possible structural division of a full-featured 3D game engine. This is especially directed for those that are reasonably experienced with 3D, but need an overview of how much work and how many parts go into a game engine.

Tools/Data
During development, handling specific data will be needed, and unfortunately it is not going to be as easy as writing some text files that define a cube. At least there will be a need to handle data generated by 3d model editors, level editors, and graphics programs.

The tools to create the raw data can be bought or are even available for free. Unfortunately there will be a need for domain specific edits and data handling that are specific to your game, tools than may not exist yet and so they will need to be created.

This can be a level editor, if one is not available that does the things required. One will probably also need to write some code to pack files into an archive since dealing with and distributing hundreds or thousands of files can be a pain. There will also be a need to write converters or plug-ins from various 3d model editors format into your own format, as all the needed tools to process game data, such as visibility computations or lightmaps.

The basic line is that you'll probably have nearly as much or more code in tools than actual game code. You can find formats and tools that you can use, but sooner or later you'll realize you need some things that are very custom to your engine and you'll end up writing your own anyway.

Although there is a probably a big rush to get tools done just so there are usable, do take care in your coding. Someone may actually try to use, extend or modify your tools one day, especially if you make your engine to be opensource or modifiable.

You should probably be prepared to spend as much time making graphics, levels, sound, music and models as you did writing the game, tools, and engine.

System
System is the part of the engine that communicates with the machine itself. If an engine is written very well the system is the only part that should need major modifications if porting to a different platform. Within the system are several sub-systems. Graphics, Input, Sound, Timer, Configuration. The System is responsible for initializing, updating, and shutting down all these sub-systems.

The Graphics Sub-System is pretty straightforward. If it deals with putting things on the screen, it goes here. One would most likely write this component using OpenGL, Direct3D, Glide, or software rendering. To get even fancier, you could implement multiple API interfaces and put a Graphics Layer on top of them to give users more choice and more chance for compatibility and performance. This is a bit difficult though, especially since not all API's will have the same feature sets.

The Input Sub-System should take all input (Keyboard, Mouse, Gamepad and Joystick) and unify it and allow for abstraction of control. For example, somewhere in the game logic, there will be a need to see if the user wants to move his or her position forward. Rather than doing multiple checks for each type of input, one would make one call to the input sub-system and it would transparently check all devices. This also allows for ease of configuration by the user, and easily having multiple inputs perform the same action.

The sound system is responsible for loading and playing sounds. Pretty straight forward, but most current games support 3D sound and this will make things a little more complex.

Pretty much everything in a 3d game engine (I'm assuming real-time games here...) is based on time. Hence you need some time management routines in the Timer sub-system. This is actually pretty simple, but since anything that moves will move with time, a decent set of routines will keep you from writing the same code over and over.

The Configuration unit actually sits above all the other sub-systems. It's responsible for reading configuration files, command line parameters, or whatever setup method is used. The other sub-systems query this system when they are initializing and running. This makes it easy to change resolution, color depth, key bindings, sound support options, or even the game that gets loaded. Making your engine very configurable just makes it easier to test and allows users to set things up the way they like.

Graphics output under Windows
Here we will discuss things like screen access under Windows. Besides that, some basic information is given on double buffering, pixel plotting and that sort of stuff.

In the old days, there was DOS. And in DOS, there was mode 13. Once initialized, the unsuspecting coder could write to video memory, starting at a fixed address, A0000 if I am correct. All this didn't block the computer, and worked on virtually every VGA card in the world. The mode allowed for output of 256 color graphics, and that was just fine, if you did it well.

But then something really bad happened. SVGA cards started to appear everywhere, and to make things worse, computers became fast enough to do true-color graphics. From that moment on, nothing was certain anymore. You had 15 bit graphics (for some VERY odd reason someone decided to ignore a whole bit), 16 bit graphics, 24 bit, 32 bit, and random orderings of the color components in these arrays of bits. You could for instance encounter a card that did RGB, but also BGR, or RGBA... So the VESA standard was invented. This made things bearable again.

As you know, as soon as a standard pops up, there's always somebody else (Microsoft) who thinks that it can be done better. So, Windows was 'presented' to the world (or shoved down our throats, just what you prefer). From that moment on, you were never certain what your processor was doing at a particular moment. It could be doing your application, but it could also switch to another 'important' application at a critical point in time for your demo... Things get worse when you surrender to Microsoft and start coding 'native' applications: Drawing to a window is a disaster, requires a 'lock', and is even slower.

OK, enough ranting. Lets try to live with what we have. I always use a buffer, because it looks so much like the old mode 13. When I have such a buffer, I try to get it to a window as efficiently as possible. This is an absolutely necessary but uninteresting step. My favorite 'toolkit' for this is MGL: A rather huge lib from SciTech, the makers of UNIVBE, a.k.a. the 'Display Doctor'. This library allows you to create a window relatively easily, and to get a pointer to it. It still requires the 'lock' however, which means that you can't debug very nicely: During the 'lock', there are no screen updates. This can be partially bypassed by using your own buffer and copying it to the window once you're done. The lock is in this case only required during the copying process, and that's usually not a big problem. There's a small snag about the MGL library: It does much more than just displaying windows. It can for example also draw lines and polygons, and it contains OpenGL stuff. Because of this unnecessary load, you have to link a 1.5Mb library to your program just to open a window... So, there's something easier, which I wish to introduce to you. It's called 'PTC', which is an abbreviation of 'Prometheus True Color', or something like that. It's a really simple Direct X wrapper, and it allows you to do full-screen graphics output at various bit depths and resolutions, and nothing more. Therefore, the library is quite small. Opening the display requires only a couple of (easy to understand and remember) commands. After that, you have full access to the display. One problem remains: The dreadful lock. This can again be bypassed using the buffer copy, however.

A big advantage of PTC that I have to mention is that it is platform independent: PTC is also available for Linux, BeOS and some other OS's. So, if your program uses PTC for it's graphics output, you are merely 'using' Windows, rather than being forced to think towards it. It makes a future move to another OS easier too, since your code will work again with minor modifications.

So, here's a bit of homework for you: Go to http://www.gaffer.org/, and fetch the PTC library. Have a look at some of the example programs, you will notice that they are really extremely simple. Once you've done that, we can proceed.

Here's a small PTC application to play with:

An explanation: Most of the stuff here will probably be quite clear. I've added a couple of lines for the buffer stuff: First I declare a buffer of the same size as the PTC display, which is copied every frame during a 'lock' to the PTC surface. This keeps the time that the surface is actually locked as short as possible, preventing hang-ups for buggy code.

Note: During the rest of this series, we will completely ignore the Windows stuff. It will be assumed that you've somehow managed to get a buffer to draw in, so that we can focus on the interesting stuff: Hardcore-3D.

3D Matrix editing
Now that we have had the nasty buffer and windows stuff, it's on to the real matter: Vector mathematics. Matrices are cool. They are also rather hard to understand fully, so if you want to know everything about them, this is the time to find a good site or book about them (preferably a site, and don't forget to submit the link to this site!).

First I want to talk about something else: Gathering knowledge. I often get e-mail from people asking me how I learned all my stuff. "What books can you recommend?" "Where did you start?", questions like that. My usual reaction to that is a chat with my wife about being 'auto-didact': You have to learn things for YOURSELF. Don't be dependent on other people's knowledge, gather your info yourself. And more important: TRY things. You won't get good by reading books, you get good by making mistakes. Gather info by browsing the web, that's the largest source of information in the world. And it's usually more up-to-date than the bookstore. Using this approach, it's possible to develop knowledge that nobody else has: You combine gathered knowledge in a unique way, allowing you to do things that nobody else did, and trying things that nobody thought of. That's how I got my (dubious) knowledge. It's kinda hard to explain, but I hope you get the point. :)

OK, back to the matrices. A matrix can be used to define a rotation in 3D space, and a translation. Therefore I usually use a 4x4 matrix: 3x3 defines an arbitrary rotation, the last column defines the movement, a.k.a. translation. Rotated coordinates can then be calculated by tossing the coordinate (vector) into the matrix.

Suppose you defined your matrix as an array of floats: Four rows by four columns, named for example cell[4][4]. You can 'toss in' a vector using the following formulas: x_rotated = cell[0][0] * x + cell[1][0] * y + cell[2][0] * z + cell[3][0] y_rotated = cell[0][1] * x + cell[1][1] * y + cell[2][1] * z + cell[3][1] z_rotated = cell[0][2] * x + cell[1][2] * y + cell[2][2] * z + cell[3][2] Note that the last row is not used, so theoretically you don't even have to store it.

So how do we create the matrix itself? We start with the identity matrix:

1  0   0   0     0   1   0   0     0   0   1   0     0   0   0   1

This matrix has the unique property that it does nothing to 3D coordinates: It leaves them perfectly intact. Then we take the desired rotation around the x-axis, which I will call 'rx' here. The matrix for this rotation looks like this:

1    0        0         0     0     cos(rx)  sin(rx)   0 0   -sin(rx)  cos(rx)   0 0    0        0         1

So, if you just wanted to rotate your 3D coordinates around the x-axis, you could use this matrix. However, if you also want to rotate around the y and z axis, you have to 'concatenate' the x rotation matrix with the y and z rotation matrix. Here they are:

y: cos(ry) 0    -sin(ry)   0 0       1     0         0     sin(ry)  0     cos(ry)   0 0       0     0         1

z: cos(rz) sin(rz)    0    0 -sin(rz) cos(rz)    0    0 0       0          1    0     0        0          0    1

OK, so how do we concatenate matrices? Here's how: Cell [x][y] of the concatenated matrix equals the sum of the rows multiplied by the columns. Some C code explains what I mean:

for (c=0; c<4; c++) for (r=0; r<4; r++) conc[c][r] = m1[0][r] * m2[c][0] + m1[1][r] * m2[c][1] + m1[2][r] * m2[c][2] + m1[3][r] * m2[c][3]; Note that the order in which you concatenate matrices is important! That's logical: If you first rotate 90 degrees around the x axis, then 45 degrees around the z axis, you get a different rotation than if you would have done these rotations in the opposite order.

That's the basic stuff. Here's how to put it in practice. Imagine you have a cube. It's located at (100,100,100) in 3D space, and should revolt around that coordinate. It's rotation is (rx, ry, rz), and of course we alter rx, ry and rz in a nice loop to have a spinning cube. The vertices of the cube can be defined as follows:

1:   -50, -50, -50     2:     50, -50, -50     3:     50,  50, -50     4:    -50,  50, -50     5:    -50, -50,  50     6:     50, -50,  50     7:     50,  50,  50     8:    -50,  50,  50

Note that the cube is initially defined at the 3D origin. That's because we wish to rotate it: If you would rotate a cube that was defined with its center at (100,100,100) it would revolt around the 3D origin also, causing a huge sweep through 3D space. The center of the cube, a.k.a. it's translation, should be the (100,100,100). So, we construct a matrix, by starting with rx. We construct another matrix, for ry, and concatenate the two. Then we construct another matrix for rz, and concatenate it. Finally the translation is added, this can be done by directly altering the relevant matrix elements, cell[3][0], cell[3][1] and cell[3][2] (for x, y and z respectively). Then we toss the vertices in the final matrix, and voilà! The rotated coordinates need to be processed of course to display them on the screen. You could use the following formula for that:

screen_x = rot_x * 500 / rot_z + 160; screen_y = rot_y * 500 / rot_z + 100; Note that I used 160 and 100 here as the centre of a 320x200 buffer. The resulting 2D coordinates can directly be plotted on your display, providing that they are NOT off screen.

OK, that's the basic stuff. Here's some more stuff to wet your appetite: You don't have to stop when you've concatenated rx, ry and rz. For example, if you have two cubes, with one circling around the other, you could define a rotation matrix with only a rotation around the x axis for the second cube. If you concatenate that matrix to the matrix of the 'parent' object, the circling cube will be rotated by the matrix of the first cube PLUS its own matrix. This makes it possible to have a 'hierarchical' system of objects: For example a robot, with arms that rotate relatively to the body of the robot (concatenate arm matrix to robot matrix), and hands rotating relative to the arm (concatenate again).

You can do other nifty things with matrices too, like inverting them. This can be used in quick surface culling, I'll talk more about that later, this article is getting a bit lengthy already.

Support
This is a system that is used by pretty much every other system in the engine. This includes all your mathematics routines, (vectors, planes, matrix, etc), memory managers, file loaders, containers (or use STL if you don't roll your own). This stuff is pretty basic and will probably be used in most any project you ever are involved in.

Renderer/Engine Core
Ah yes, everyone loves rendering 3D graphics. Because there are so many different methods of rendering 3D worlds, it's nearly impossible to give a description of a graphics pipeline that works in all situations.

Regardless of how you implement your renderer, the most important thing is to make your renderer component based and clean. Make sure you have distinct modules for different things. The sub-sections that I break the renderer into are sections like Visibility, Collision Detection and Response, Camera, Static Geometry, Dynamic Geometry, Particle Systems, Billboarding, Meshes, Skybox, Lighting, Fogging, Vertex Shading, and Output.

Each one of these sections needs to have an interface that easily allows for changes in settings, position, orientation, or any other setting that may be associated with the system.

One major pitfall to look out for is feature bloat. Decide what you are going to implement at the design stage. If you don't adding new features will start to get hard to do and the solutions will be kludgy.

One thing that is nice and convenient is to have all triangles (or faces) ultimately pass through the same point in the render pipeline. (Not a triangle at a time, I'm talking about triangle lists, fans, strips, etc.) It takes a bit more work to get everything into a format that can be passed through the same lighting, fogging, and shading code but in the end you'll be happy that any effect that you can do to one polygon can be done to any polygon in your game simply by changing its material/texture id.

It doesn't hurt to have multiple points from which things are drawn, but it can lead to redundant code if you're not careful.

You'll eventually find out that all those cool effects that you wanted to implement will be 15% or less of the total code you end up writing. That's right, most of a game engine is not graphics.

Data structures for 3D Graphics
I'm working on Focus, a light-weight 3D engine experiment that I merely use to try out little things like bilinear interpolation, shadows and fast software rendering in general. This little engine is of course not my first engine, and that's why I want to talk a little about 3D data structures. I've discovered that the main reason for dropping an engine and starting over from scratch is 'bad design'. Rewriting is no problem of course: Starting from scratch often improves code, since you can rewrite stuff that you painfully wrote in an earlier engine rather quickly, and usually with far less ugly and more efficient code. Earlier engines often had limitations that I could only get rid of by making heavy changes, or rewriting. Most of these limitations merely consisted of limitations in the data structures. Some examples:

One of my first 3D engines (the E3Dengine) was coded completely in Pascal. Polygons where internally stored as four-sided convex polygons, since my world only consisted of squares, so that seemed fine at first. After some months of coding, I had an indoor rendering engine, with 6DOF (that was before the release of Quake, by the way) and I encountered my first major problem: Clipping against the Z=0 plane. This is necessary for an indoor engine, since polygons often are partially behind you (as opposed to object rendering engines, where the entire object is usually in front of you). Vertices behind the camera do weird things when you apply perspective to them: Remember the perspective formulas from the previous article, where the rotated x and y coords where divided by their depth. The x and y coords are negated by this formula as soon as they pass z=0, and ON z=0, the formula causes a 'divide by zero'. The problem with clipping something off a polygon is that the polygon gets extra or less vertices. My structures could cope with 3 vertices, but not with 5... In this case, I could have increased the space in all the arrays to 5 vertices for each polygon, but that messed up my assembly routines, since they expected certain data to be at fixed positions in memory.

Learned lessons:
 * Never use assembler in the early stages of engine development. In Pascal, it was sometimes necessary to use it nevertheless, but the latest C++ compilers really make assembler something to be used ONLY as a last optimization step.

 * Never use fixed values for things like the number of vertices in a polygon. More general: Make data structures extendible.

More recent engines had other limitations: Object records couldn't cope with a hierarchical system of objects, polygon records couldn't be easily expanded to hold bump data, and so on. So I guess you might learn something from my scars...

A modern 3D engine needs quite some data, at different levels. Here's what I think you need (top-down):

1. World Structure 2. Sector (Local) Structure 3. Object Structure 4. Polygon Structure

In the ideal case, all this should be as generic as possible, to avoid too much rewriting resulting in possible demotivation and leaving of the 3D scene of a talented new coder. :) That's a bad thing.

OK, on with the details. On the top level (world structure) you should think about how you would organize a world, if you would ever build an engine that needs something like that. I mean, if you are a beginner, you will probably begin with an object renderer, just like I did. So it might be tempting to regard this object as a 'world', since there is no other data to process anyway. You might just declare an array of vertices, rotate them, and dump them to the screen. Fine. But think about this: If your array of vertices would have been stored in a larger structure, called an 'object', you would be tempted (probably) to try to get your engine to work with TWO or even more objects. Here are some things that you should take into account when you are figuring out a good world structure for you:

A world is probably too big to display or even process every frame. So you need some structure that allows partial processing. Unseen world parts and objects must preferably not be taken into account.

That means that there must be a link between the world, and the objects in it. Otherwise you would be rendering all objects, plus the visible part of the world, which could still be far too much work.

You might also want to have a more or less dynamic world. That asks for different data structures again. Here's how I would implement the top level:

class World {    SectorList* sectors; }; And here's what a sector looks like:

class Sector {    PolygonList* polygons; ObjectList* objects; };

Most engines work like this: Even a BSP engine. This way, objects are linked directly to the world, as long as they are stored in the right sector every time they move. So the problem of object visibility is now directly linked to the world visibility problem.

The next level you should think about (or the first level, if you're only doing an object engine) is the object data structure. Here's a sample structure:

class Object {    PolygonList* polies; ObjectList* childs; Matrix matrix; };

There are some interesting things in this structure. First, I always put a pointer to a list of objects in this structure. There's a good reason for this: Many objects are linked in some way. If they are, their matrices are usually determined in an incremental way: An arm for example rotates relative to a torso, and thus it needs both its own matrix, and the matrix of its parent (the torso). The torso itself is probably rotated relative to the world: Therefore I also put a matrix in the Object class.

OK, one more level down, the polygon level. Here's a basic polygon class:

class Polygon {    VertexList* vertices; Texture* texture; Sector* sector; Plane plane; }; And the vertex class:

class Vertex {    Coordinate* position; float U, V;    }; Finally, the coordinate class:

class Coordinate {    Vertex original; Vertex rotated; boolean processed; };

This is interesting stuff, since even beginning coders will encounter this. Let's start with the polygon class: In this case I have used a VertexList class to hold my vertices. This makes it possible to have an arbitrary number of vertices in a polygon, but there's a drawback: Each list entry also has a 'next' pointer (assuming that it is a linked list). Thus, each vertex takes 4 more bytes than you would expect. If that's not a big problem, consider this: The alternative is an array. An array is stored sequentially, and is usually better for the cache. But an array is fixed size... In Focus, I finally chose the array approach. Therefore, you MUST specify the number of vertices when instantiating the polygon. My polygon class looks like this:

class Polygon {    Vertex** vertices; int vertices; Texture* texture; Sector* sector; Plane plane; };

So, there is a single pointer to a block of memory that holds pointers to vertices. Note that I still use extra memory: An integer for the number of vertices (since there's no NULL pointer at the end of a list any more), and a pointer to the block of pointers.

Another thing to note in the polygon class is the sector pointer. This is used for portal polygons: Since a portal links two sectors, this is the place where you should store this information.

Finally, there is a plane structure. You could also make this a plane pointer, if you want to re-use the plane (for example, if you have a lot of polygons in the same plane). In case you don't know what to do with planes: I'll talk more about that in a later article.

Recycling is also the reason for storing a coordinate pointer in the Vertex class. A cube has eight vertices, but the six sides all have 4 vertices, making a total of 24 vertices. In the cube case, it is obvious that the 3D position of only eight vertices are unique. The texture coordinates however need not be shared by two polygon vertices at the same position. Therefore, a vertex class should contain U/V information (the texture coordinates), and a pointer to a 3D position. This saves space and processing time, since a rotated vertex doesn't have to be rotated again. This brings me to the coordinate class:

In the coordinate class there's maybe a bit more than you would expect. First, there's both an original vector and a rotated vector. You need to keep the original to ensure maximal accuracy: Even high precision floating point arithmetic will introduce numerical instability quickly when you rotate coordinates again and again. The other interesting thing is the 'processed' field: It indicates whether a vertex has been rotated for the current frame or not. This eliminates duplicate rotations.

Here's a small tip for more advanced coders: Instead of a boolean you could also use an integer. If you store the current 'frame ID' in this integer (just increase it each frame) you don't have to reset the 'processed' flag for all rotated vertices each frame. This is particularly handy when it's not so easy to determine which vertices of a huge set where rotated at the end of the drawing process.

OK, that's what I wanted to say about 3D data structures. My intention is to get you thinking about this at an early stage: The way you setup your data is probably the most important decision you make in the design of your engine. Actual tips in short are: Use pointers and lists, and as few arrays as possible. Arrays look simple at first, but they soon make your engine more complicated and force you to do ugly things that C++ was not designed for.

Example of coding a wireframe cube
I can rant about PTC and windows programming, data structures and so on, but in the end there's nothing like a good example. Well, I've just coded a very small program (54 lines of code, in fact) that just shows a wireframe cube, and that might be just what you need. Here's the code:

#include "ptc.h"      #include "math.h"       float angle, x[8], y[8], z[8], rx[8], ry[8], rz[8], scrx[8], scry[8];

void line (unsigned short* buf, float x1, float y1, float x2, float y2) { double hl=fabs(x2-x1), vl=fabs(y2-y1), length=(hl>vl)?hl:vl; float deltax=(x2-x1)/(float)length, deltay=(y2-y1)/(float)length; for (int i=0; i<(int) length; i++) { unsigned long x=(int)(x1+=deltax), y=(int)(y1+=deltay); if ((x<640)&&(y<480)) *(buf+x+y*640)=65535; }      }

void render (unsigned short* buf, float xa, float ya, float za) { float mat[4][4];            // Determine rotation matrix float xdeg=xa*3.1416f/180, ydeg=ya*3.1416f/180, zdeg=za*3.1416f/180; float sx=(float)sin(xdeg), sy=(float)sin(ydeg), sz=(float)sin(zdeg); float cx=(float)cos(xdeg), cy=(float)cos(ydeg), cz=(float)cos(zdeg); mat[0][0]=cx*cz+sx*sy*sz, mat[1][0]=-cx*sz+cz*sx*sy, mat[2][0]=cy*sx; mat[0][1]=cy*sz, mat[1][1]=cy*cz, mat[2][1]=-sy; mat[0][2]=-cz*sx+cx*sy*sz, mat[1][2]=sx*sz+cx*cz*sy, mat[2][2]=cx*cy; for (int i=0; i<8; i++)    // Rotate and apply perspective { rx[i]=x[i]*mat[0][0]+y[i]*mat[1][0]+z[i]*mat[2][0]; ry[i]=x[i]*mat[0][1]+y[i]*mat[1][1]+z[i]*mat[2][1]; rz[i]=x[i]*mat[0][2]+y[i]*mat[1][2]+z[i]*mat[2][2]+300; scrx[i]=(rx[i]*500)/rz[i]+320, scry[i]=(ry[i]*500)/rz[i]+240; }         for (i=0; i<4; i++)         // Actual drawing { line (buf, scrx[i], scry[i], scrx[i+4], scry[i+4]); line (buf, scrx[i], scry[i], scrx[(i+1)%4], scry[(i+1)%4]); line (buf, scrx[i+4], scry[i+4], scrx[((i+1)%4)+4], scry[((i+1)%4)+4]); }      }

int APIENTRY WinMain (HINSTANCE hInst, HINSTANCE hPrevInst, LPSTR lpCmdLine, int nCmdShow) { for (int i=0; i<8; i++)     // Define the cube { x[i]=(float)(50-100*(((i+1)/2)%2)); y[i]=(float)(50-100*((i/2)%2)), z[i]=(float)(50-100*((i/4)%2)); }         Console console;            // Initialize PTC and start rendering Format format (16, 31<<11, 63<<5, 31); console.open ("3D", 640, 480, format); Surface surface (640, 480, format); while (!console.key ) { unsigned short* buf=(unsigned short*) surface.lock ; memset (buf, 0, 640*480*2); render (buf, angle, 360-angle, 0); angle+=0.2f; if (angle==360) angle=0; surface.unlock; surface.copy (console); console.update; }         return 0; } Please take a moment to get this stuff running. Using VC5 or 6, create a new Win32 application with no files in it. Add the PTC lib file to the project (using add files) and the ptc.h header file, and of course the source that I just showed. Next you have to disable the inclusion of two default libraries (under the 'linker input settings'), LIBC and LIBCD. Now the program should compile just fine. You might try to make it slightly more readable by splitting lines that do multiple variable initializations on a single line. :)

So what does this program do? Let's start with the program entry, which is in this case the WinMain function. The first thing that happens here is the definition of a cube. A cube has eight vertices, which could be initialized as follows:

1. x: -50 y: -50 z: -50 2. x: 50 y: -50 z: -50 3. x: 50 y:  50 z: -50 4. x: -50 y: 50 z: -50 5. x: -50 y: -50 z: 50 6. x: 50 y: -50 z:  50 7. x: 50 y:  50 z:  50 8. x: -50 y: 50 z:  50

The weird construction with the modulo operators does just that (only shorter:). If you take a moment to visualize this data, you'll see that these are 8 vertices centered around (0, 0, 0), which is handy, because rotations are easy around the origin of 3D space.

After that, we need to set up PTC. I used a 16 bit display in this case, at a resolution of 640x480 pixels. This video mode should work on most computers.

In the main loop the function 'render' is called, with a pointer to the PTC buffer and the rotation around the three axes as input. Note that the rotations are passed in degrees.

The 'render' function is slightly more interesting. Let's see what it needs to do: Ultimately it should draw lines between the rotated vertices, and those lines should be somewhere near the centre of the screen. Rotations are done using a matrix. If you forgot how that worked, browse back to the article that discusses them. As you know, a rotation around three axes can be performed by calculating the matrix for the rotation around each axis, and them concatenating them. In this case, I have done the concatenation for you: The matrix 'mat' is filled with sins and cosines at once. I encourage you to alter the code so that the final matrix is calculated by concatenating the separate matrices, so that you can also rotate around the axes in a different order.

The rotated vertices are still centred at the origin. Since perspective calculations do a nice divide by the z coordinate, we need to move the object away from the camera. This is done by adding 300 to the rotated z. Note that you could also add something to x and y: This is how you rotate an object around something else than the origin. In this case, the object is effectively rotated around (0, 0, 300).

Finally, the perspective is calculated. Note that the object is also centred on screen, by adding 320 to the screen-x coordinate, and 240 to the screen-y coordinate.

Now the lines can be drawn to the screen. The line function that I included is very short, and that's the only thing that is good about it. If you need fast code, ditch this function, and include your own assembler bresenham code. Some comments about this code:

It first determines how many pixels need to be drawn. If the line has a higher vertical than horizontal range, it draws abs(y2-y1) pixels, otherwise abs(x2-x1). This prevents gaps.

When drawing pixels, each subsequent screen location can be calculated by adding something to the first x-coordinate (x1) and to the first y-coordinate (y2). This 'something' is actually the x or y range, divided by the total number of pixels to be drawn. When you think about it, it's logical that you reach (x2,y2) after adding 'n' times a bit to x and y, where 'n' is the calculated number of pixels. Also note that either 'delta-x' or 'delta-y' is exactly 1.

If you want to play a bit around with this code, then here are some suggestions:

 * Editor's Note: Feel free to submit any modified versions of this program that you make, and I'll probably post it here with your name.

Alter the line drawing code so that it accepts other colours. Currently the colour is always 65535, which is pure white in a 16 bit colour mode. This colour consists of red, green and blue: Red is 5 bits, green 6, and blue 5. The final colour is calculated with the following formula: red*2048+green*32+blue. Note that red should be an integer between 0 and 31, and so is blue. Green is an integer between 0 and 63.

Play a little with the position of the object. It can also be partially off-screen, the line drawing code doesn't crash.

Try to create something else than a cube. Using this code you could design your own name in glorious 3D.

Extend the data structures so that the connections between vertices are no longer hard coded. You could for example define edges, which should hold a start and an end vertex. Then the rendering code should draw all the edges, which should make the code much nicer if you have a lot of edges. You could also introduce 'polygons', which hold more than two vertices.

Add a cube, and use the stuff from the matrices document to make the second cube spin around the first. To get this right, construct the second cube around (100,0,0), so that the rotation causes it to 'swing' around the first cube.

Liquids
Simulating water or other liquids can be extremely hard if realism is intended. Water details changes in regards to how near the observer is, if may have foam, transparency, distortion and specularity. Water surfaces tend to be reflective, random and extremely complex to mimic when the player can interact with it or the physics are changeable, for instance replicating the splash of debris or alterations to the environment that contains the liquid.

Console
Ok, I know everyone likes to follow the crowd and have a console like Quake. But it's really a good idea. With console variables and functions you can change settings in your game and your engine without restarting it. It's wonderful for outputting debug information while developing. Oftentimes you'll be needing to examine some variables and outputting the to the console is faster and sometimes better than running a debugger. Once your engine is running, if an error occurs, you don't have to quit the application; you can handle it gracefully and just print an error message. If you don't want your end user to see or use the console, its easy to disable it and no one is the wiser that it's still there.

Game Interface
The most important part of a 3D game engine is that it is a game engine. It is not a game. The actual game should never have components that are put into the game engine. Having a thin layer between the engine and the game makes for cleaner code and ease of use. It's a little extra code, but it also makes a game engine very reusable and it becomes much easier to use a scripting language for game logic, or put the game code in a library. If you embed any of your game logic in the engine itself, don't plan on reusing it later without lots of problems and modifications.

So you are probably wondering what this layer between the engine and game provides. The answer is control. For each part of the engine that has any dynamic properties, the engine/game layer provides an interface to modify it. Some things in this category include the camera, model properties, lights, particle system physics, playing sounds, playing music, handling input, changing levels, collision detection and response, and placement of 2D graphics for a heads up display, title screen or whatever. Basically if you want your game to be able to do it, there must be an interface into the engine to do it.


text:
Template:Semiconductors/Page

 Semiconductors /Templates

title: Template:Semiconductors/Page


text:
Template:MIPS Assembly/Page

 MIPS Assembly ''This template is the general TOC template for the MIPS Assembly wikibook. This template will appear on the main page of the book, and will appear at the top of every page, so it should be kept short.''

title: Template:MIPS Assembly/Page


text:
MIPS Assembly/MIPS Architecture

The MIPS architecture
MIPS is a register based architecture, meaning the CPU uses registers to perform operations on. There are other types of processors out there as well, such as stack-based processors and accumulator-based processors.

Registers are memory just like RAM, except registers are much smaller than RAM, and are much faster. In MIPS the CPU can only do operations on registers, and special immediate values.

MIPS processors have 32 general purpose registers, but some of these are reserved. A fair number of registers however are available for your use. For example, one of these registers, the program counter, contains the memory address of the next instruction to be executed. As the processor executes the instruction, the program counter is incremented, and the next memory address is fetched, executed, and so on.

Why MIPS?
The MIPS architecture is a Reduced Instruction Set Computer (RISC). As a RISC architecture, it doesn't assign individual instructions to complex, logically intensive tasks. This is in contrast to complex instruction set computer (CISC) architectures like the DEC VAX, which had an instruction to multiply polynomials and another to perform a cyclic redundancy check (CRC), often used in TCP/IP. At the time, it was thought that implementing such instructions in hardware would result in performance increase for programs that used them, even if it resulted in highly complex processor design. MIPS and other RISC architectures were based on the philosophy that, among other things, by only implementing a small core (only a few dozen instructions, instead of several hundred) of the most common instructions, architects could simplify the design and speed up the majority of common instructions so much that the cost of implementing complex programs as multiple instructions would be hidden.

Much has been written on the RISC versus CISC debate,   so for our purposes we shall focus on the consequences of the MIPS design choices:

 * All MIPS instructions are 32 bits long.
 * This makes hardware for accessing and decoding instructions straightforward.
 * This also means there are a finite number of instructions.
 * All MIPS instructions belong to one of three instruction formats. This makes decoding instructions simple for both humans and hardware.  Since the instruction format is regular, it doesn't take much work to learn most of the MIPS instruction set.

MIPS Philosophies

 * Simplicity favors regularity
 * Good design demands good compromise
 * Smaller is faster
 * Make the common tasks the fastest

title: MIPS Assembly/MIPS Architecture


text:
MIPS Assembly/MIPS Instructions

Writing assembly code
An assembly language program has a few common features. These are:

 * labels
 * sections
 * directives
 * comments
 * commands

Comments
In MIPS assembly, comments are denoted with a number sign ("#"). Everything after that sign on the same line is a comment and is skipped by the assembler's lexer.

Labels
A label is something to make your life simple. When you reference a piece of your program, instead of having to count lines, you can just give it a name. You use this in loops, jumps, and variable names.

Labels don't appear in your final code, they're only there for convenience, one of the few perks you'll get from the typical MIPS assembler. It also makes life easy for the assembler, because it can now easily go around relocating and linking code. Don't worry if you don't know what those are, that'll come later.

Labels in MIPS assembly, actually in most variants of ASM as well, are created by writing

name:

where name is a name you use to refer to this label. Note that, you can't create a label with the same name as a MIPS instruction.

Labels are the same as their C cousins, the targets of goto operators.

Sections
A section is a way of dividing an assembly language program up into the instructions and the data logically. Since your assembly program is loaded into memory, all the processor needs to know is the start of execution (known as the entry point) and merely just increments the instruction pointer and continues along. If data is interspersed in the instruction code in memory, the processor needs to know what is data and what is instructions - which serves for a much more complicated processor. For simplicity, the data is set off in a different area than the instructions. Sections are used for this purpose.

There are two sections you need to be mindful of in MIPS programming: the text and data sections. The text section holds your assembly program, and the data section holds your data. One designates a text section by starting with .text and the start of a data section by .data.

Directives
The processor assembler (or your emulator) understands a few special commands that perform specific tasks to make your life easier: for example creating memory space for you to store data in variables.

If you wish to create a variable for a number in your assembly program, you may want to:
 * 1) switch to the data section
 * 2) create a label to create a memory reference for your variable
 * 3) give it an appropriate name
 * 4) allocate some memory for it
 * 5) align it properly in memory.
 * 6) switch back to the text section

From what we have learned, we can write the MIPS assembly code up to step 3:

But now how can we allocate some memory? We use the .space directive. An integer takes up 4 bytes, usually, so we write We need to align the data in memory now (we'll explain this below), so we use the .align directive And we've switched back to the text section.

Memory locations in MIPS assembler need to be aligned - that is, that memory locations must begin on the correct location otherwise the processor will crash. 4-byte integers must be aligned every 4 bytes, and so on. The .align n directive aligns the data to a memory cell fit for 2n bytes. Therefore, for 32-bit (4-byte) integers we use .align 2 for 22 or 4 bytes. Aligns the next variable or instruction on a byte that is a multiple of number. To align the space allocated, the 'align n' should come before the 'space x' declaration. For example, here is a sample for allocating 6 words (6 x 4 = 24 bytes) in memory and aligning them at word boundaries

title: MIPS Assembly/MIPS Instructions


text:
Talk:MIPS Assembly

I've created a page-header template for use on every page in this book:

 * Template:MIPS Assembly Page

--Whiteknight (talk) (projects) 17:26, 25 May 2006 (UTC)

I have also created a template for listing MIPS instructions, and telling their type (R, I, J):

 * Template:MIPS Instruction

--Whiteknight (talk) (projects) 20:13, 25 May 2006 (UTC)

title: Talk:MIPS Assembly


text: Template:MIPS Assembly/Instruction

title: Template:MIPS Assembly/Instruction


text:
MIPS Assembly/Arithmetic Instructions

Register Arithmetic Instructions
This instruction adds the two operands together, and stores the result in the destination register. Negative numbers are handled automatically using two's complement notation, so different instructions do not need to be used for signed and unsigned numbers.

The sub instruction subtracts the second source operand from the first source operand, and stores the result in the destination operand. In pseudo-code, the operation performs the following:

rd := rs - rt

Both add and sub trap if overflow occurs. However, some programming systems, like C, ignore integer overflow, so to improve performance "unsigned" versions of the instructions don't trap on overflow.

Multiplication and Division
The multiply and divide operations are slightly different from other operations. Even if they are R-type operations, they only take 2 operands. The result is stored in a special 64-bit result register. We will talk about the result register after this section.

This operation multiplies the two operands together, and stores the result in rd. Multiplication operations must differentiate between signed and unsigned quantities, because the simplicity of Two's Complement Notation does not carry over to multiplication. The mult instruction multiplies and sign extends signed numbers.

The result of multiplying 2 32-bit numbers is a 64-bit result. We will discuss the 64-bit results below.

The multu instruction multiplies the two operands together, and stores the result in rd. This instruction is for unsigned numbers only, and does not sign extend a negative result. This operation also creates a 64-bit result.

The div instruction divides the first argument by the second argument. The quotient is stored in the lowest 32-bits of the result register. The remainder is stored in the highest 32-bits of the result register. Like multiplication, division requires a differentiation between signed and unsigned numbers. This operation uses signed numbers.

Like the div instruction, this operation divides the first operand by the second operand. The quotient is stored in the lowest 32-bits of the result, and the remainder is stored in the highest 32-bits of the result. This operand divides unsigned numbers, and will not sign-extend the result.

64-Bit Results
The 64-bit result register is broken into two 32-bit segments: HI and LO. We can interface with these registers using the mfhi and mflo operations, respectively.

Takes only 1 operand. This instruction moves the high-32 bits of the result register into the target register.

Also takes only 1 operand. Moves the value from the LO part of the result register into the specified register.

If the upper (most significant) 32 bits of a product are unimportant to computation, programmers may save a step by using instructions that discard the upper 32 bits.

There is no unsigned version of the mul instruction. The mul instruction may also clobber the existing values in HI and LO.

Register Logic Instructions
These operations perform bit-wise logical operations on their operands.

Performs a bitwise AND operation on the two operands, and stores the result in rd.

Performs a bitwise OR operation on the two operands, and stores the result in rd.

Performs a bitwise NOR operation on the two operands, and stores the result in rd.

Performs a bitwise XOR operation on the two operands, and stores the result in rd.

Immediate Arithmetic Instructions
These instructions sign-extend the 16-bit immediate value to 32-bits and performs the same operation as the instruction without the trailing "i".

To subtract, use a negative immediate.

Immediate Logic Instructions
All logical functions zero-extend the immediate.

Takes the bitwise AND of rs with the immediate and stores the result in rt.

Takes the bitwise OR of rs with the immediate and stores the result in rt.

Takes the bitwise XOR of rs with a the immediate and stores the result in rt.

Shift instructions
Logical shift left: rd ← rt << shamt. Fills bits from right with zeros.

Logical shift right: rd ← rt >> shamt. Fills bits from left with zeros.

Arithmetic shift right. If rt is negative, the leading bits are filled in with ones instead of zeros: rd ← rt >> shamt.

Because not all shift amounts are known in advance, MIPS defines versions of these instructions that shift by the amount in the rs register. The behavior is otherwise identical.

title: MIPS Assembly/Arithmetic Instructions


text:
MIPS Assembly/Control Flow Instructions

Jump Instruction
The jump instructions load a new value into the PC register, which stores the value of the instruction being executed. This causes the next instruction read from memory to be retrieved from a new location.

The j instruction loads an immediate value into the PC register. This immediate value is either a numeric offset or a label (and the assembler converts the label into an offset).

The jr instruction loads the PC register with a value stored in a register. As such, the jr instruction can be called as such:

jr $t0

assuming the target jump location is located in $t0.

Jump and Link
Jump and Link instructions are similar to the jump instructions, except that they store the address of the next instruction (the one immediately after the jump) in the return address ($ra; $31) register. This allows a subroutine to return to the main body routine after completion.

Like the j instruction, except that the return address is loaded into the $ra register.

The same as the jr instruction, except that the return address is loaded into a specified register (or $ra if not specified)

Example
Let's say that we have a subroutine that starts with the label MySub. We can call the subroutine using the following line:

jal MySub ...

And we can define MySub as follows to return to the main body of the parent routine:

jr $ra

Branch Instructions
Instead of using rt as a destination operand, rs and rt are both used as source operands and the immediate is sign extended and added to the PC to calculate the address of the instruction to jump to if the branch is taken.

Branch if rs and rt are equal. If rs = rt, PC ← PC + 4 + imm.

Branch if rs and rt are not equal. If rs ≠ rt, PC ← PC + 4 + imm.

Branch if rs is greater than or equal to zero. If rs ≥ 0, PC ← PC + 4 + imm.

Branch if rs is less than or equal to zero. If rs ≤ 0, PC ← PC + 4 + imm.

Branch if rs is greater than zero. If rs > 0, PC ← PC + 4 + imm.

Branch if rs is less than zero. If rs < 0, PC ← PC + 4 + imm.

Set Instructions
These instructions set rd to 1 if their condition is true. They can be used in combination with beq and bne and $zero to branch based on the comparison of two registers.

If rs < rt, rd ← 1, else 0.

If rs < imm, rd ← 1, else 0. The immediate is sign extended.

If rs < rt, rd ← 1, else 0. Treat rs and rt as unsigned integers.

If rs < imm, rd ← 1, else 0. The immediate is sign extended, but both rs and the extended immediate are treated as unsigned integers. The sign extension allows the immediate to represent both very large and very small unsigned integers.

title: MIPS Assembly/Control Flow Instructions


text:
MIPS Assembly/Memory Instructions

Load and store instructions use a special syntax:

instr rt, imm(rs)

The memory address used for the load or store is rs + imm. The immediate is sign-extended.

Load Instructions
Loads a byte and does not sign-extend the value.

Loads a halfword, or two bytes, and does not sign-extend the value. The halfword must be aligned (i.e., it must start at an even address).

Loads a word (four-bytes) from memory. The word must be aligned (i.e., the last two bits of the address must be zero).

Store Instructions
Stores the least significant (rightmost) byte of rt to memory.

Stores the least significant (rightmost) halfword of rt to memory.

Stores the contents of rt in memory.

title: MIPS Assembly/Memory Instructions


text:
MIPS Assembly/Floating Point Instructions

Arithmetic
Integer implementation of floating-point addition


text:
MIPS Assembly/MIPS Details

Registers
MIPS has 32 general-purpose registers and another 32 floating-point registers. Registers all begin with a dollar-symbol ($). The floating point registers are named $f0, $f1, ..., $f31. The general-purpose registers have both names and numbers, and are listed below. When programming in MIPS assembly, it is usually best to use the register names.

In general, there are many registers that can be used in your programs: the ten temporary registers and the eight saved registers, and the arg $a and return-value $v registers. Temporary registers are general-purpose registers that can be used for arithmetic and other instructions freely (call clobbered), while saved registers must keep their value across function calls. (If you want to use one, you have to save it on procedure entry, and restore at procedure exit). The easiest way to handle the call-preserved $s0..7 registers is to not touch them at all.

Temporary register names all start with a $t. For instance, there are $t0, $t1 ... $t9. this means there are 10 temporary registers that can be used without worrying about saving and restoring their contents. The saved registers are named $s0 to $s7.

The zero register, is named $zero ($0), and is a static register: it always contains the value zero. This register may not be used as the target of a store operation, because its value is hardwired in, and cannot be changed by the program.

There are also several registers to which the programmer does not have direct access with most instructions. Among these are the Program Counter (PC), which stores the address of the instruction executing (read by JAL to calculate a return address, written by jumps and branches), and the "hi" and "lo" registers, which are used in multiplication and division, which have results longer than 32 bits (multiplication may result in a 64-bit product and division results in a quotient and remainder). There are special instructions to move data to and from the hi and lo registers.

Instruction Formats
There are 3 instruction formats: R Instructions, I Instructions, and J Instructions.

R Instructions
R Instructions take three arguments: two source registers (rt and rs), and a destination register (rd). R instructions are written using the following format:

 * instruction rd, rs, rt

where each one stands for as follow:

For example,

add $t0, $t1, $t2

Adds the values of $t1 and $t2 and stores the result in $t0.

When assembled into machine code, an R instruction is represented as follows:

For R-format instructions, the opcode, or "operation code" is always zero. rs, rt, and rd correspond to the two source and one destination registers, respectively. shamt is used in shift instructions instead of rt to make the hardware simpler. In assembly, to shift the value in $t4 two bits to the left and place the result in $t5:

sll $t5, $t4, 2

Since the opcode is zero for all R-format instructions, func specifies to the hardware exactly which R-format instruction to execute. The add example above would be encoded as follows:

opcode rs   rt     rd   shamt funct 000000 01001 01010 01000 00000 100000

Since it is an R-format instruction, the first six bits (opcode) are 0. The next 5 bits correspond to rs, which in this example is $t1. From the table above, we find that $t1 is $9, which in binary is 01001. Likewise, the next five bits encode $t2 = $10 = 01010. The destination is $t0 = $8 = 01000. We are not performing a shift, so shamt is 00000. Finally, since the func for the add instruction is 100000.

For the shift example above, the opcode field is again 0 since this is an R format instruction. The rs field is unused in shifts, so we leave the next five bits at 0. The rt field is $t4 = $12 = 01100. The rd field is $t5 = $13 = 01101. The shift amount, shamt, is 2 = 00010. Finally, the func field for sll is 000000. Thus, the encoding for sll $t5, $t4, 2 is:

opcode rs   rt     rd   shamt  funct 000000 00000 01100 01101 00010 000000

I Instructions
I instructions take two register arguments and a 16-bit "immediate" value. An immediate is a value that is stored as part of the instruction instead of in memory. This makes accessing constants much faster than if we had to put constants in memory and then load them (hence the name). I-format instructions, like R-format instructions, specify the target register (rt) first. Next comes one source register (rs) and finally the immediate value.

 * instruction rt, rs, imm

For example, let's say that we want to add the value 5 to the register $t1, and store the result in $t0:

addi $t0, $t1, 5

Or compare-and-branch to a nearby label (range is 16-bit signed displacement, left shifted by 2). The assembler calculates `(target - branch_insn_address + 4) >> 2` as the immediate:

beq $t0, $zero, t0_equals_zero_branch_target

I-format instructions are represented in machine code as follows:

The opcode specifies which operation is requested. rs and rt are five bits each, as before, and in the same positions as the R-format instructions. The imm field holds the immediate value. Depending on the instruction, the immediate constant may either be sign-extended or zero-extended. If a 32-bit immediate is needed, a special instruction, lui ("load upper immediate") exists for loading an immediate into the upper 16 bits of a register. That register can then be logically ORed with another 16-bit immediate to store the final value in that register. That value can then be used in normal R-format instructions. The following sequence of instructions stores the bit pattern 0101 0101 0101 ... into register $t0:

lui $t0, 0x5555 ori $t0, $t0, 0x5555

Typically, the assembler will automatically split 32-bit constants in this way so the programmer doesn't have to worry about it if you write li $t0, 0x5555555. Some assemblers (like MARS with extended pseudo-instructions mode enabled) even support large immediates for addi / addiu / xori / etc. this way.

The addi example from above would be encoded as follows. The addi instruction has an opcode of 001000. The source register, $t1, is number 9, or 01001 in binary. The target register, $t0, is number 8, or 01000 in binary. Five is 101 in binary, so addi $t0, $t1, 5 in machine code is:

opcode  rs   rt           imm 001000 01001 01000 0000 0000 0000 0101

addi and addiu sign-extend their 16-bit immediate to 32 bits (so can represent signed 2's complement values from -32768 .. 32767, i.e. unsigned values of 0..0x7fff and 0xffff8000 .. 0xffffffff)

Bitwise boolean logical instructions like andi, ori, and xori zero-extend the immediate (so can use values from 0..65535)

Other instructions that use the I format include load/store (address = register + signed 16-bit displacement), compare-immediate such as slti $t1, $t0, 1234 (producing a 0 or 1 in a register), lui for loading an immediate to the upper 16 bits of a register, and branch (but not jump) instructions.

J Instructions
J instructions are used to transfer program flow to a given hardcoded absolute address within the 256MB region around the PC register. J instructions are almost always written with labels: the assembler and linker will convert the label into a numerical value. A J instruction takes only one argument: the address to jump to.

(Truly PC-relative control transfers can be done instead with 'b label' that are usable in position-independent code. MIPS branch instructions are I-format instructions with a 16-bit relative displacement, left-shifted by 2, unlike jumps.)

instruction addr

There are two J-format instructions: j and jal. The latter will be discussed later. The j ("jump") instruction tells the processor to immediately skip to the instruction addressed by addr. To example, to jump to a label1:

j label1

A J-format instruction is encoded as

On MIPS32 machines, addresses are 32-bits wide, so 26 bits may not be enough to specify which instruction to jump to. Fortunately, since all instructions are 32-bits (four bytes) wide, we can assume that all instructions start at a byte address that's divisible by 4 (we are in fact guaranteed this by the loader). In binary, a number that is divisible by 4 ends with two zeros (just like a number that's divisible by 100 in decimal always ends in two zeros). Therefore, we can allow the assembler to leave out the last two zeros and have the hardware reinsert them. This effectively makes the address field 30 bits. The final four bits will be borrowed from the address of the next instruction, so we cannot let a program straddle a 256MB boundary, because a jump across the boundary would require a change in the 4 uppermost bits. (The PC while a J instruction is processed has already been updated to point to the next instruction, the branch-delay slot.)

In the example above, if label1 specified an instruction as address 120, or 1111000 in binary, we can encode the jump example above in machine code as follows. The opcode for j is 2, or 10 in binary, and we must chop off the last two bits of the jump address, leaving it at 11110. Thus, the machine code for j 120 is:

opcode |---addr---| 000010 0000 0000 0000 0000 0000 0111 10

title: MIPS Assembly/MIPS Details


text:
MIPS Assembly/Instruction Formats

This page describes the implementation details of the MIPS instruction formats.

R Instructions
R instructions are used when all the data values used by the instruction are located in registers.

All R-type instructions have the following format:

OP rd, rs, rt

Where "OP" is the mnemonic for the particular instruction. R instructions all use the opcode 0, with the function in the funct field. rs, and rt are the source registers, and rd is the destination register. As an example, the add mnemonic can be used as:

add $s1, $s2, $s3

Where the values in $s2 and $s3 are added together, and the result is stored in $s1. In the main narrative of this book, the operands will be denoted by these names.

R Format
Converting an R mnemonic into the equivalent binary machine code is performed in the following way:

 * opcode:The opcode is the machinecode representation of the instruction mnemonic. The opcode field is 6 bits long (bit 26 to bit 31) but always set to 0 in the R format. The actual instruction to perform is placed in the funct field.
 * rs, rt, rd:The numeric representations of the source registers and the destination register. These numbers correspond to the $X representation of a register, such as $0 or $31. Each of these fields is 5 bits long. (25 to 21, 20 to 16, and 15 to 11, respectively). Interestingly, rather than rs and rt being named r1 and r2 (for source register 1 and 2), the registers were named "rs" and "rt" for register source, register target and register destination.
 * Shift (shamt):Used with the shift and rotate instructions, this is the amount by which the source operand rs is rotated/shifted. This field is 5 bits long (6 to 10).
 * Funct:In R format instructions, the opcode is always zero, and the funct parameter contains the code for the different instructions. 6 bits long (0 to 5). For instance, to add numbers in two registers and place the result in a third, the opcode will be set to zero and the function to 0x20.

I Instructions
I instructions are used when the instruction must operate on an immediate value and a register value. Immediate values may be a maximum of 16 bits long. Larger numbers may not be manipulated by immediate instructions.

I instructions are called in the following way:

OP rt, rs, IMM

However, sw and lw instructions are called in the following way: OP rt, IMM(rs)

Where rt is the target register, rs is the source register, and IMM is the immediate value. The immediate value can be up to 16 bits long. For instance, the addi instruction can be called as:

addi $s1, $s2, 100

Where the value of $s2 plus 100 is stored in $s1.

I Format
I instructions are converted into machine code words in the following format:

 * Opcode: The 6-bit opcode of the instruction. In I instructions, all mnemonics have a one-to-one correspondence with the underlying opcodes. This is because there is no funct parameter to differentiate instructions with an identical opcode. 6 bits (26 to 31)
 * rs, rt: The source and target register operands, respectively. 5 bits each (21 to 25 and 16 to 20, respectively).
 * IMM:The 16 bit immediate value. 16 bits (0 to 15). This value is usually used as the offset value in various instructions, and depending on the instruction, may be expressed in two's complement.

J Instructions
J instructions are used when a jump needs to be performed. The J instruction has the most space for an immediate value, because addresses are large numbers.

J instructions are called in the following way:

OP LABEL

Where OP is the mnemonic for the particular jump instruction, and LABEL is the target address to jump to.

J Format
J instructions have the following machine-code format:

 * Opcode:The 6 bit opcode corresponding to the particular jump command. (26 to 31).
 * Address:A 26-bit shortened address of the destination. (0 to 25). The full 32-bit destination address is formed by concatenating the highest 4 bits of the PC (the address of the instruction following the jump), the 26-bit pseudo-address, and 2 zero bits (since instructions are always aligned on a 32-bit word).

FR Instructions
FR instructions are similar to the R instructions described above, except they are reserved for use with floating-point numbers:

FI Instructions
FI instructions are similar to the I instructions described above, except they are reserved for use with floating-point numbers:

Opcodes
The following table contains a listing of MIPS instructions and the corresponding opcodes. Opcode and funct numbers are all listed in hexadecimal.

title: MIPS Assembly/Instruction Formats


text:
MIPS Assembly/Pseudoinstructions

The MIPS instruction set is very small, so to do more complicated tasks we need to employ assembler macros called pseudoinstructions.

List of Pseudoinstructions
The following is a list of the standard MIPS instructions that are implemented as pseudoinstructions:

 * abs
 * blt
 * bgt
 * ble
 * neg
 * negu
 * not
 * bge
 * li
 * la
 * move
 * sge
 * sgt

Branch Pseudoinstructions
Branch if less than (blt)

The blt instruction compares 2 registers, treating them as signed integers, and takes a branch if one register is less than another.

blt $8, $9, label

translates to

slt $1, $8, $9 bne $1, $0, label

Other Pseudoinstructions
Load Immediate (li)

The li pseudo instruction loads an immediate value into a register.

li $8, 0x3BF20

translates to

lui $at, 0x0003 ori $8, $at, 0xBF20

Absolute Value (abs)

The absolute value pseudo instruction loads the absolute value contained in one register into another register.

abs $1, $2

translates to

addu $1, $2, $0 bgez $2, 8 (offset=8 → skip 'sub' instruction) sub $1, $0, $2

Move (move)

The move pseudo instruction moves the contents of the second register operand into the first register operand.

move $1, $2

translates to

add $1, $2, $0

Load Address (la)

la $a0,address

translates to  lui $at, 4097 (0x1001 → upper 16 bits of $at). ori $a0,$at,disp

where the immediate (“disp”) is the number of bytes between the first data location (always 0x 1001 0000) and the address of the first byte in the string.

Set on greater than or equal (sge)

The sge instruction compares 2 registers, treating them as signed integers, and sets a given register($1) if the value of the 1st register($8) >= the value of the 2nd register($9), else the given register($1) == 00.

sge $1, $8, $9

translates to

addiu $9, $9, -0x01 slt $1, $9, $8

title: MIPS Assembly/Pseudoinstructions


text:
MIPS Assembly/Register File

Registers
MIPS has 32 general-purpose registers and another 32 floating-point registers. Registers all begin with a dollar-symbol ($). The floating point registers are named $f0, $f1, ..., $f31. The general-purpose registers have both names and numbers, and are listed below. When programming in MIPS assembly, it is usually best to use the register names.

Zero Register
The zero register ($zero or $0) always contains a value of 0. It is built into the hardware and therefore cannot be modified.

$at Register
The $at (Assembler Temporary) register is used for temporary values within pseudo commands. It is not preserved across function calls. For example, with the (slt $at, $a0, $s2) command, $at is set to one if $a0 is less than $s2, otherwise it is set to zero.

$v Registers
The $v Registers are used for returning values from functions. They are not preserved across function calls.

Argument Registers
The $a registers are used for passing arguments to functions. They are not preserved across function calls.

Temporaries
The temporary registers are used by the assembler or assembly language programmer to store intermediate values. They are not preserved across function calls.

Saved Temporaries
Saved Temporary registers are used to store longer lasting values. They are preserved across function calls.

$k Registers
The k registers are reserved for use by the OS kernel. They may change randomly at any time as they are used by interrupt handlers.

Pointer Registers

 * Global Pointer ($gp) - Usually stores a pointer to the global data area (such that it can be accessed with memory offset addressing).
 * Stack Pointer ($sp) - Used to store the value of the stack pointer.
 * Frame Pointer ($fp) - Used to store the value of the frame pointer.
 * Return Address ($ra) - Stores the return address (the location in the program that a function needs to return to).

All Pointer Registers are preserved across function calls.

title: MIPS Assembly/Register File


text:
MIPS Assembly/Exceptions

This page is going to talk about exception handling. We will also talk about what exceptions are, and what causes them.

title: MIPS Assembly/Exceptions


text:
Talk:Video Game Design/Programming/Framework/2D vs 3D/3D Engine

* (cur) (last) 08:13, 26 April 2006 Ashvidia * (cur) (last) 05:56, 25 April 2006 RHaworth (move to Wikibooks context) * (cur) (last) 00:02, 25 April 2006 Ashvidia
 * (cur) (last) 20:25, 12 May 2006 71.192.105.211 (removed author name a) [rollback] [proxycheck]

* (cur) (last) 03:42, 9 May 2006 Ashvidia [rollback] [proxycheck] * (cur) (last) 16:10, 3 May 2006 CmdrObot m (sp (15): efficently→efficiently, neccessary→necessary, unneccessary→unnecessary, wich→which) * (cur) (last) 05:49, 25 April 2006 RHaworth (move to Wikibooks context) * (cur) (last) 00:19, 25 April 2006 Ashvidia m   * (cur) (last) 00:18, 25 April 2006 Ashvidia m    * (cur) (last) 23:51, 24 April 2006 Ashvidia

Microsoft bashing seems inappropriate and un-scholarly for this sort of article

 * I think it adds some humor and personality to otherwise dry subject matter. I do however think this is too short to be considered a book by any stretch of the imagination. It's more of an article or pamphlet. 24.17.229.241 (discuss) 19:30, 26 November 2011 (UTC)
 * I agree and I'm a die hard Linux user. Humor yes, bashing, no. Lets try to be a little more classy than bashing.

Chunks are complex and unapproachable

 * Lets be honest, large chunks of code are terrifying if you are new to this.

Referencing other books

 * There is no point in rehashing what other books have done well already. the book OpenGL Programming has done a fantastic job at teaching how to get started with OpenGL. This book is on building a 3D engine, I'm assuming that means an engine like UDK, Unity, or Blender Game Engine. While the 3D rendering system is highly highly important, lets not waste time trying to do a better job at what OpenGL Programming has done. And if OpenGL programming is lacking some where, go add to it so that the good resources are centralized. We can add what is inappropriate for the OpenGL programming here.


text:
Talk:A-level Physics/Cosmology/Stars and Galaxies

 * 1) describe the nuclear fusion processes taking place within the Sun.✔
 * 2) calculate the energy released as a result of the fusion processes taking place within the Sun.
 * 3) understand and use the magnitude scales for stars and galaxies.✔
 * 4) recall and use the equation m = -2.5 lg I + constant, where m is the apparent magnitude and I is the intensity.
 * 5) understand the concept of absolute magnitude M.✔
 * 6) recall and use the inverse square law to derive the relation between apparent magnitude, absolute magnitude and distance: m - M = 5 lg (r/10).
 * 7) recall and use the relationship m - M = 5 lg (r/10).✔
 * 8) sketch and interpret a Hertzsprung-Russell diagram of absolute magnitude plotted against temperature in order to recognise and identify different classes of star.
 * 9) describe how clouds of gas, consisting mainly of hydrogen and helium, form into young Main Sequence stars.✔
 * 10) describe the probable evolution of the Sun into a red giant and represent this evolution on a Hertzsprung-Russell diagram.
 * 11) recall that the Main Sequence stars may evolve into red giants, white dwarfs, supernovae, neutron stars or black holes.✔
 * 12) recall and understand that the nuclear processes occurring in a star, the time it spends on the Main Sequence and its ultimate fate depends on its mass.✔
 * 13) describe the structure of our own Galaxy and the Sun’s position in it.
 * 14) explain qualitatively how other galaxies differ from our own.
 * 15) recall and use Newton’s law of Gravitation to relate the mass of a galaxy to orbital speed within it.

Carried over from Talk:A-level_Physics/Cosmology/Models_of_the_known_universe

8. show awareness of the principal contents of the Universe, including stars, galaxies and radiation.

11. recall the distances involved between objects in the Universe, including distance to nearest stars, distance across a galaxy, size of observable Universe.

12. appreciate the range of magnitudes of the sizes and masses of objects in the Universe.

Isnt there a mistake on the page?? i parallax is 1/3600th of a degree right??


text:
MIPS Assembly/MIPS Processors

This page is going to talk about some of the specific MIPS implementations, and MIPS relatives.

Most MIPS implementations use the classic 5 stage pipeline: instruction fetch, instruction decode/register fetch, execute, memory access, and register write back.

title: MIPS Assembly/MIPS Processors


text:
MIPS Assembly/Introduction

This page is going to serve as a general foreword about this book.

What This Book is About
This book is going to discuss the MIPS assembly language. This book will cover not only the straightforward facet of this subject (how to program MIPS), but will also look deeper, and discuss MIPS from a very low level. In this way, this book should be useful both for people just learning to program MIPS, and also to people who are looking to do advanced tasks in MIPS (such as write a MIPS assembler program, or construct a low-level OS kernel in MIPS). This book will not talk about the specifics of MIPS hardware, however.

Who This Book is For
This book is designed to be a reference for all people who are interested in MIPS. This book starts off with the basics behind the language, and discusses the various operations in such a manner that beginners will be able to get a handle of MIPS programming. However, this book also contains a number of advanced sections for experienced programmers who are looking at doing advanced projects with the MIPS architecture.

How This Book is Organized
This book is organized in such a fashion that the most simple material is presented first, and the most advanced material is saved towards the end. The first section of the book is reserved for historical and interesting information about MIPS, and listings of real-world MIPS implementations. The second section is going to go into the MIPS assembly language, talking about each instruction individually, and explaining how to use them. The third section is going to talk about the topics of programming, assembling, and emulating MIPS code. Finally, the fourth section is going to talk about advanced topics, such as the internal machine code of MIPS machines, the nature of pseudoinstructions, some advanced system instructions, and handling exceptions.

Where to Go From Here
This book will serve as a complete reference to programming MIPS. While there are no Wikimedia resources specifically designed to follow this text, the reader may benefit from reading about higher-level languages, or assemblers, or another advanced programming topic.

For more information about how to design MIPS and other types of microprocessor systems, see Microprocessor Design.

title: MIPS Assembly/Introduction


text:
Cookbook:Rice with Milk (Arroz con Leche)

Arroz con leche is a sweet dish of creamed rice.

Ingredients

 * 1 cup uncooked rice
 * 2 cups water
 * 7 cups milk
 * 2 cinnamon sticks
 * 2 cups white granulated sugar or fruit syrup
 * ½ tsp salt
 * Outer peel of 1 lemon (remove white pith)
 * Cinnamon powder
 * Mint leaves (optional, for garnish)

Procedure

 * 1) Put the rice in a strainer and rinse it until the water runs clear.
 * 2) Put the rice in a pot with the water, and boil it for 7 minutes until the rice softens and the water is almost completely absorbed.
 * 3) Add the milk, the sticks of cinnamon, and the lemon peel. Boil over moderate heat for 10 minutes. Take the cinnamon sticks and the lemon peel out, and cook for another 5–6 minutes until the rice is softer, stirring often with a wood spoon.
 * 4) Add the sugar, and cook for another 30 minutes; then add the salt, and cook for 1–2 more minutes, stirring often.
 * 5) Take the rice mixture off the heat and place it in a deep glass dish, sprinkle with cinnamon powder, and refrigerate.

Notes, tips, and variations

 * Soy milk, rice milk, or almond milk can be used instead of milk.
 * Can be served with vanilla, chocolate, or Neapolitan ice cream, or with non-dairy ice creams.


text:
User:Omi~enwikibooks

Welcome to my userspace. I am General Eisenhower from Wikipedia.

Hi.

title: User:Omi~enwikibooks


text: Transwiki:B+ Tree Java Implementation

title: Transwiki:B+ Tree Java Implementation


text:
Algorithm Implementation/Trees/B+ tree

In computer science, a B+ tree is a type of tree data structure. It represents sorted data in a way that allows for efficient insertion and removal of elements. It is a dynamic, multilevel index with maximum and minimum bounds on the number of keys in each node.

A B+ tree is a variation on a B-tree. In a B+ tree, in contrast to a B tree, all data are saved in the leaves. Internal nodes contain only keys and tree pointers. All leaves are at the same lowest level. Leaf nodes are also linked together as a linked list to make range queries easy.

The maximum number of keys in a record is called the order of the B+ tree.

The minimum number of keys per record is 1/2 of the maximum number of keys. For example, if the order of a B+ tree is n, each node (except for the root) must have between n/2 and n keys.

The number of keys that may be indexed using a B+ tree is a function of the order of the tree and its height.

For a n-order B+ tree with a height of h:
 * maximum number of keys is $$n^h$$
 * minimum number of keys is $$2(n/2)^{h-1}.$$

The B+ tree was first described in the paper "Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972)".

Sample implementation in C++
CAREFUL: THE FOLLOWING CODE EXAMPLES DO NOT IMPLEMENT A PROPER B+-TREE. While they are very similar to a B+-Tree, they do not fulfill the B+-Tree criteria (as the authors admit in some comments).

This code snippet has been tested under Linux on a 32-bit x86 computer. Deletion of keys has not been implemented yet. It can be done quite easily in a lazy way with an amortized cost of O(log n), by rebuilding the tree from scratch every time that there are as many deleted keys as non-deleted keys. The rebuilding can be done in O(n) time, so its amortized cost is only O(1). This approach, however, would not be appropriate for real time systems.

The implementation uses the Boost library to have compile-time assertions and efficient memory allocation. The latter could be done with the  instead, resulting in some performance penalty.

Violate the B+Tree definition during inner node split
After convert it into Java code, I realize the following code doing split insertInner violate the B+ Tree definition For example, what if N = 4, so after you split, we end up with 3 nodes, root node with 1 key, original node with 1 key, and the sibling node with 3 keys. So it (original node) violates the B+ Tree rules at least half full in the inner node. Look like we still need the canonical algorithm to make it right. Not shortcut here. So this algorithm is not strict B+ Tree, but it works. Anyway, I convert above C++ code to Java code shown below.

It doesn't really work because generic arrays cannot be created by casting from a newly created array of a concrete ancestor like Object.

ie. T[] a = new T[10] won't work. see the field declarations of LNode.

title: Algorithm Implementation/Trees/B+ tree


text:
Cookbook:Bløtkake (Norwegian Berries and Cream Cake)

| Cuisine of Norway | Desserts

Bløtkake is a traditional Norwegian dessert, usually reserved for special occasions such as birthdays. It is also served on Norway's national day, May 17th.

Batter

 * 4 eggs
 * 100 g white granulated sugar
 * 100 g flour
 * 1 tsp baking powder

Filling

 * Raspberry jam
 * 1 tin sliced peaches
 * Vanilla custard
 * Whipped cream
 * 1 tsp white granulated sugar

Garnish

 * Berries or other fruit (usually blueberries, redcurrants or other soft berries)

Procedure

 * 1) Whip the eggs and sugar until they form peaks. Sieve the flour and baking powder into the egg mixture and fold in gently.
 * 2) Pour the batter into a greased round tin (about 22 cm in diameter) ,and bake the cake at 170°C for 30–40 minutes.
 * 3) Cool completely on a rack, then unmold the cakes.
 * 4) Slice the cake horizontally into 3 layers. Sprinkle each slice with some of the peach juice from the tin.
 * 5) Cover 2 of the slices with jam, peach slices, and vanilla custard. Place the third layer on top of the other two.
 * 6) Whip the cream with the sugar. Cover the whole cake, including the sides, with the whipped cream.
 * 7) Garnish with berries and/or fruit.


text:
Cookbook talk:Bløtkake (Norwegian Berries and Cream Cake)

* (cur) (last) 16:55, 12 February 2006 Ehjort m   * (cur) (last) 16:55, 12 February 2006 Ehjort * (cur) (last) 16:45, 15 December 2005 W.marsh (this is just a recipe) * (cur) (last) 00:02, 11 December 2005 Dapoloplayer * (cur) (last) 02:43, 10 December 2005 Jorvik29
 * (cur) (last) 14:31, 25 March 2006 Jon513 m (egg disambig) [rollback] [proxycheck]


text:
Cookbook:Buffalo Chicken Sandwich

A Buffalo chicken sandwich is a sandwich consisting of pieces of boneless Buffalo chicken and blue cheese on a submarine sandwich style roll. The recipe is for one sandwich. It can be doubled, tripled, quadrupled, etc., but fry the chicken one piece at a time.

Ingredients

 * Oil for frying
 * ½ cup flour
 * ½ teaspoon salt
 * ½ cup milk
 * 1 boneless skinless chicken breast, pounded flat
 * 1 hamburger bun
 * 1 leaf green leaf lettuce
 * 2 tomato slices
 * 1 red onion sliced (if it's strong, only use a few rings)
 * 2 tablespoon hot sauce
 * Blue cheese dressing

Procedure

 * 1) Heat just enough oil to cover chicken to 350 °F (175°C) in a large frying pan or a deep-fryer.
 * 2) Stir together flour and salt. Dredge chicken in milk, then flour mixture, again in milk, then flour a second time. Refrigerate chicken for 10–15 minutes.
 * 3) Deep fry chicken in oil for 10 minutes or until golden brown. Drain on a rack.
 * 4) Toast or grill the face of the bun.
 * 5) Put chicken in a bowl with a lid. Add hot sauce, put lid on, and shake gently to coat.
 * 6) Put chicken on bun and top with lettuce and tomato. Serve open face, with blue cheese dressing on the side.

title: Cookbook:Buffalo Chicken Sandwich


text:
Cookbook talk:Buffalo Chicken Sandwich

* (cur) (last) 02:32, 30 April 2006 Pwt898 m   * (cur) (last) 21:19, 16 March 2006 Demilio (This is just a recipe.) * (cur) (last) 09:05, 9 November 2005 Infrogmation m (Reverted edits by 169.139.224.10 to last version by Bluebot) * (cur) (last) 10:34, 8 November 2005 169.139.224.10 * (cur) (last) 02:31, 31 October 2005 Bluebot m (Fixed See also/External links error(s).) * (cur) (last) 09:13, 11 October 2005 169.139.224.10 * (cur) (last) 09:18, 5 October 2005 169.139.224.10 * (cur) (last) 09:12, 5 October 2005 169.139.224.10 * (cur) (last) 12:46, 21 August 2005 Missmarple m (cat) * (cur) (last) 16:15, 27 January 2005 Boothinator * (cur) (last) 15:59, 27 January 2005 128.235.249.80
 * (cur) (last) 11:11, 30 April 2006 Wavy G m (I don't know much about recipes, but I'm pretty sure a chicken sandwich is not "also called a 'cheese'".) [rollback] [proxycheck]

title: Cookbook talk:Buffalo Chicken Sandwich


text:
MIPS Assembly/MIPS Assemblers

This page is going to list some assemblers for programming in MIPS, and will discuss how to program using MIPS assemblers.

/edit by Till Fischer, University of Ulm (Germany)

Heres a link to a Download of the MARS, an emulation Assembler Program by the Missouri State University, we use that one in our Studies in order to learn Assembler: http://courses.missouristate.edu/KenVollmar/MARS/

title: MIPS Assembly/MIPS Assemblers


text:
MIPS Assembly/MIPS Emulation

This page is going to talk about using MIPS emulators to test MIPS code on a non-MIPS computer.

A common MIPS Emulator is Spim which is fully cross platform. Another one is MIPS Assembler and Simulator, which has been successfully deployed in and used in a few high schools. QEMU is another common emulator environment for MIPS. Yet another Emulator is MARS a cross-platform Java MIPS IDE.

Open Virtual Platforms (OVP) http://www.OVPworld.org includes the freely available simulator OVPsim, a library of models of processors, peripherals and platforms, and APIs which enable users to develop their own models. The models in the library are open source, written in C, and include the MIPS 4K, 24K and 34K cores. These models are created and maintained by Imperas http://www.imperas.com and in partnership with MIPS Technologies have been tested and assigned the MIPS-Verified(tm) mark. Sample MIPS-based platforms include both bare metal environments and platforms for booting unmodified Linux binary images. These platforms/emulators are available as source or binaries and are fast, free, and easy to use. OVPsim is developed and maintained by Imperas and is very fast (100s of million instructions per second), and built to handle multicore architectures. To download the MIPS OVPsim simulators/emulators visit http://www.OVPworld.org/mips.

title: MIPS Assembly/MIPS Emulation


text:
Portuguese Grammar/Crase

Definition
Crase (from greek krâsis, "mixture", "blend") refers to the contraction of two vowels. In Portuguese, only two vowels "a" can make up a crase, the first "a" being the preposition a (to, at, in, for) and the second "a" must be the first character of the next word. This phenomenon occurs in the following situations:

 * 1) The preposition a before the definite article a ("the", feminine, regardless number);
 * 2) The preposition a before the determiners aquele, aquela or aquilo ("that"), regardless of gender and number.

Aquele is used to refer masculine words.

Aquela is used to refer feminine words.

Aquilo is like aquelas coisas ("those things").

Notice
Sometimes the contraction with the article a occurs even when the next word is implicit/hidden. This situation happens when the hidden word is moda ("mode", "fashion"), maneira ("manner", "way"), a.s.o.

Examples
1. Vou à festa de aniversário de Maria.
 * I'm going to Mary's birthday party.

2. Diga àquele homem para parar de beber.
 * Tell that man to stop drinking.

3. Saída à francesa.
 * Exit without saying farewell. (An idiom; literally, "Exit in the French way / Exit à la French".)

Explanation
The verb ir (to go, irregular) is constructed with the preposition a. Since the mentioned party (festa) is a specific party (Mary's), one uses the definite article. Festa is a feminine word so it receives the article a. This way:
 * Vou a a festa → Vou à festa (a+a = à)

Errors in using crase
Some people write à caminho, à não ser.

But this is not correct because caminho ("way") is a masculine word and não ("no", "not") and ser ("to be") are not nouns.

To be continued.

Author: Daniel Simas Barros

Edited by: Alexandre D. Almeida

title: Portuguese Grammar/Crase