Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!

1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Member Since 03 Apr 2007
Offline Last Active May 16 2015 07:36 PM

Topics I've Started

802.11 Ad-hoc vs Infrastructure: Latency, throughput, and scaling.

15 October 2010 - 09:46 AM


I have a situation where a number of computers in close proximity (in a single room, in fact) need to communicate with one another. They happen to be robots, but they might as well be PCs at a LAN party. They have 802.11 adapters, and I'm trying to understand the tradeoffs involved between ad-hoc and infrastructure mode wireless networking.

Infrastructure mode gives you a star topology. Ad-hoc gives you a complete graph (it's a good assumption in this example that all stations really can talk to one another). All agents are two hops apart with infrastructure, but only one hop away with ad-hoc. Advantage: Ad-hoc?

I've read contradictory things about throughput. Some sources imply that the halved latency of ad-hoc also means double throughput vs infrastructure mode (this doesn't make sense to me). Others say that you get 54 Mbps in infrastructure and only 11 Mbps in ad-hoc. Who's right? Advantage: Infrastructure?

Scaling (Collisions)
Despite the different network topologies of infrastructure and ad-hoc, the physical reality is that all stations are sharing the same medium for either one -- so you'd expect roughly the same number of collisions with either, and in both cases this scales with the square of the number of stations, right? If anything, since twice the hops are required to get a packet from point A to point B in infrastructure mode, would you expect fewer collisions in ad-hoc mode? Advantage: Ad-hoc?

Thanks in advance for sharing any insight.

[Edited by - Emergent on October 16, 2010 12:28:58 AM]

C++ templated struct multidimensional arrays

25 July 2010 - 07:58 AM


I'm interested in efficient ways to implement multidimensional, rectangular arrays in C++, whose dimensions are known at compile time, and which can be allocated on either the stack or the heap. What I'd like is for templates to do as much of the indexing work at compile time as possible.

What I really don't like, is the pointers-to-pointers approach that you commonly see recommended, and which many common libraries use (e.g., Boost multidimensional arrays, STL vectors-of-vectors). What I prefer is a contiguous block of memory, with a little index arithmetic -- like what C compilers generate behind the scenes for multidimensional arrays on the stack.

One way to do this is by building structs of appropriate sizes, and multidimensional arrays as structs-of-structs; then the compiler will allocate memory in contiguous blocks and generate offsets into this block of memory as appropriate. An implementation might look like,

template <int size, class T> struct Array
T data[size];
inline T& operator()(const int i)
return data[i];
template <int dim1, int dim2, class T> struct Array2
Array<dim1, T> data[dim2];
inline T& operator()(const int i1, const int i2)
return data[i2](i1);
//...likewise for Array3, Array4, etc...

Clearly, with a little copying-and-pasting, you can quickly make for yourself an array with as many dimensions as you want. The problem, of course, is the copying and pasting. Hence my question for someone more skilled at template metaprogramming than I is, how can I get the compiler to generate all these types automatically?

The alternative is to compute indexes more explicitly, like,

int N = 4; // # of dimensions of array
int S[] = {10, 32, 40, 28}; // Width of array in each dimension
int x[] = {4, 10, 7, 9}; // N-dimensional index into array

// Compute linear index 'i'
int i = 0;
int k = N;
i = S[k]*i + x[k];
}while(k != 0);

// Now i is the linear index into the array.

and hope that the compiler unrolls this and implements it efficiently. But this isn't as nice as the struct method IMO...

So, any thoughts?

Editing a release binary...

18 June 2010 - 06:10 AM


I've got a closed-source program, compiled without debug symbols, whose behavior I would like to tweak for my own personal use. Specifically, the program provides a network service that I want, but creates a window that I do not want; I would like to be able to launch the program invisibly at startup.

Presumably, the window is created by a call to either CreateWindow or (more likely) CreateWindowEx, in which case I just need to make sure that the 'WS_VISIBLE' bit in 'dwstyle' is set to zero (which can be achieved just by setting the whole DWORD to zero). So that's the one change I want to make: change the fourth argument to CreateWindowEx to zero.

Hence my first question is: If a program is compiled without debug symbols, is it still possible to identify when it is calling which Windows API functions? (for instance, can it be done using the debugger in Visual Studio 2008?) Is there a good way to locate the call to CreateWindow or CreateWindowEx? (Later on in this post, I'll describe my attempts to figure this out.)

Before continuing, let me note that ordinarily, I wouldn't go through all this trouble. The way I would normally run a program invisibly is to just call ShellExecute from a little C++ program with the 'nShowCmd' argument set to SW_HIDE. Equivalently (and this is what I actually tried), I'd use 'shell.Run' from the Windows Scripting Host with the second (intWindowstyle) argument set to zero, like so:

// start-server.js
// Invisibly launches server
"use strict";
var shell = WScript.CreateObject("WScript.Shell");
shell.Run("server.exe -start", 0, false);

However, programs are not required to respect the intWindowstyle argument, and what is interesting is that although this program will listen if I tell it to run minimized, or maximized, or normally, it will not listen if I tell it to run invisibly. This is what leads me to modify the program itself.

So let's dive in.

I opened up the EXE in the Visual Studio debugger, and by stepping through it found exactly where the window is created - I think. I find the call trace,

00481397 call 0048F5D7
0048F5E7 call 00490590
004905F9 call dword ptr [eax+50h]
004011A6 call 00490B1C
00490BF8 call 00493505
00493576 call 00493C9D
00493CAB call dword ptr ds:[49E43Ch] (server.exe)
7E42AF60 call dword ptr [edx] (user32.dll)

where I have represented levels of nested functions with indentation. The innermost function call (I haven't gone any deeper) creates a window without any buttons, and appears to be being made by user32.dll. The preceding function call, which then seems to be into user32.dll, is made by the program itself. Hence, assuming I've interpreted things correctly, the line that I'm looking for is,
00493CAB  call        dword ptr ds:[49E43Ch]

This line exists in the function starting at 00493C9D, so let me show the code from the start of this functon to the function call (plus two lines afterward):
00493C9D  mov         eax,dword ptr [ecx+38h] 
00493CA0 test eax,eax
00493CA2 jne 00493CB3
00493CA4 push dword ptr [esp+4]
00493CA8 push dword ptr [ecx+1Ch]
00493CAB call dword ptr ds:[49E43Ch] <------------- CreateWindow(Ex)?
00493CB1 jmp 00493CC1
00493CB3 mov edx,dword ptr [eax]

Now there seems to be a contradiction: Only two things are pushed on the stack prior to the call to ds:[49E43Ch], which would imply that it is a function that only takes two arguments. Both CreateWindow and CreateWindowEx take many more arguments than this!

Hence, if anyone has any insights for what might be going on here (and where I might have gone astray), I'd appreciate them too.


"Points at infinity:" Hyperbolic space?

27 May 2010 - 05:30 AM

I'm looking for a nice way to represent and to talk about "points at infinity" in a particular sense. I.e., I want to compactify R^n in a certain way, and I'd like to know what this compactification is called and if there's a convenient way to work with it. I think it might be hyperbolic space, H^n, but there are a few things I haven't been able to figure out if that's the case. Not projective space It's probably easiest to describe what I want by saying what I don't want: Whereas real projective space identifies "opposite infinities" with one another, I would like them to be separate. Two constructions A construction Disk method Here's a construction for what I want: Identify R^n with the open unit ball B^n in R^n via the diffeomorphism phi:B^n-->R^n defined,
phi(p) = ------------- p .
          1 - ||p||^2
Moreover, define the distance between two points by d(p1,p2) = ||phi(p1) - phi(p2)|| . What I'd like, now, is the closed ball with this metric. (This requires allowing the metric to take values in the extended reals, but I think that's ok.) Homogeneous coordinates Another construction would use homogeneous coordinates. However, whereas real projective space RP^n can be constructed in this way using the equivalence relation
(x1,w1) ~ (x2,w2) <==> There exists a real number 'y' s.t.
                       (x1,w1) = y (x2, w2) ,
what I want would require
(x1,w1) ~ (x2,w2) <==> There exists a positive real number 'y' s.t.
                       (x1,w1) = y (x2, w2) .
Hyperbolic space? All this is extremely similar to either the Klein model or the Poincare disk model for hyperbolic space, so I think this might be what I actually want. My problem, if this is the case, is that in order for this to be useful I need an isometry from R^n with the Euclidean metric, to the Poisson/Klein disk with associated metric. I.e., in order to compactify R^n, I need to know what the right way to map it to the disk is. I don't think that the answer is a conformal map, because these preserve angles, which I don't care about. What I want is something that preserves distances -- i.e., an isometry. Questions - Is what I want actually hyperbolic space? If so, what's the isometry from R^n to the open Poincare or Klein disk? (Or how can I figure this out?) - If what I want is not hyperbolic space, what is it? Thanks in advance everybody for any replies! :-) [Edited by - Emergent on May 27, 2010 12:18:10 PM]

"Special" character support?

25 February 2010 - 07:41 AM

Hi, I've noticed a usability problem on the forums, and I'm not sure if it's Firefox or the forum code itself that is to blame. The issue is that many commonly-used characters are handled inconsistently. The most problematic one is the plus sign, "+," which cannot be typed as-such; instead the HTML character code #43 must be used. As mentioned, however, this behavior is inconsistent. For instance, when editing a post where character codes were used, the text box contains not those codes as typed, but rather the characters they represent -- which means that one must again go through the post and replace all instances of certain characters by their codes. This is even more problematic and inconsistent in "source" UBB tags: I find that there, the usual plus character can be used (as opposed to the HTML character code) the first time the post is written, but the post cannot be edited: If the plus character is used in the edit, it simply appears as a blank space in the post, and if the character code is used, then it appears in the post as the code rather than as the character. If this only occurred for certain "strange" characters like letters-with-accents, this would not be much of a problem. But for a character as commonly used as the plus sign, it's real usability problem. Do other people have these issues?