1
\$\begingroup\$

How can I find stack position without using stack pointer you were given with upper bound of stack and depth of stack using embedded C or assembly language for 8051. Can anybody please help me finding the answer.

\$\endgroup\$
  • \$\begingroup\$ So you get one end of the stack, and the size,and want to find the other end? \$\endgroup\$ – PlasmaHH Sep 27 '16 at 9:34
  • \$\begingroup\$ @PlasmaHH Stack grows downwards right. Thats why its said 'depth' the starting is called upperbound (07H). So without noting the SP, I have to tell where the stack position is now(after some operation). That is, size is given, start point is given. Without using the stack pointer how to tell where is the current stack position is. \$\endgroup\$ – Harikrishnan V Nair Sep 27 '16 at 10:00
  • \$\begingroup\$ is the depth the max depth, or the current depth? because if it is the current depth the SP is simply the (sum|difference) of the starting address and the current depth. Say you start from 0x07ff growing down, and current size is 0xf, then SP is at 0x07f0 (or 0x07ef if SP points to the first free location) \$\endgroup\$ – Vladimir Cravero Sep 27 '16 at 10:11
  • \$\begingroup\$ It's a stupid question, only valid iff the architecture and compiler is specified. \$\endgroup\$ – pipe Sep 27 '16 at 12:03
  • 1
    \$\begingroup\$ @pipe, agreed. I guess that if it's a job interview question, they are just looking to see how you would start solving the problem, what kind of thought processes are going on in your head, do you get stuck, do you ask for help, do you give quick but incorrect answer, or take forever before admitting that you can't do it yourself, things like that. They might also be assessing your general knowledge about microcontrollers, or the 8051 architecture, or of compilers and stack layouts in general... \$\endgroup\$ – PkP Sep 27 '16 at 12:16
7
\$\begingroup\$

As noted in the comments, not using the stack pointer when there is one is really silly and nobody would ever do it in real life. Just like writing a FizzBuzz program.

Yes, you do need knowledge of processor architectures, but that's not the main thing the interviewers want to know. They could find out that by just asking you knowledge questions.

What the question is really about is your approach to problem solving: Do you just say that you don't know? Do you just sit there silently, apparently doing nothing, before announcing that you don't know? Do you start to cry? Do you try to talk (with the interviewers or with yourself) about the problem in order to discuss and/or dismiss the different ways to approach the problem? Do you start to sketch your options on paper or draw a mind-map? These are the things which the interviewers will be looking at, and some of them make a better impression than others.


So here's the uninteresting part of the answer, the algorithm:

  1. Push a known value on the stack, say 0x77.
  2. Scan the whole stack space for this value (you know start and maximum size of the stack).
  3. Once you find 0x77 somwhere, execute a POP instruction and push 0x88.
  4. Check that memory address again. If it changed to 0x88, that's the top of your stack. Go to 6.
  5. If it didn't change, continue scanning and repeat steps 3-5 until you reach the end of the stack or find a changing value.
  6. Execute a POP to clean up after yourself.

Note: If you don't know the location and size of the stack, you could also scan the whole address space, which likely isn't that big in a micro controller. You just need to be careful that your implementation uses no RAM, lest it places the searched value somewhere outside of the stack and confuses itself.

\$\endgroup\$
  • \$\begingroup\$ +1 ,it looks like , you are the one how made the question for the interview :)) \$\endgroup\$ – ElectronS Sep 27 '16 at 12:31
  • \$\begingroup\$ +1, you've done better than me. :) \$\endgroup\$ – PkP Sep 27 '16 at 12:39
  • \$\begingroup\$ How do you push a value onto the stack without having the stack pointer? \$\endgroup\$ – silverscania Sep 27 '16 at 12:41
  • \$\begingroup\$ Oh I see there is a specific push instruction for the 8051 \$\endgroup\$ – silverscania Sep 27 '16 at 12:43
  • \$\begingroup\$ This is likely why "you were given with upper bound of stack and depth of stack" was mentioned. \$\endgroup\$ – pipe Sep 27 '16 at 12:49
1
\$\begingroup\$

This is actually a pure programming question, but alas...

You can find the location of the stack by placing a variable on the stack, then take the address of the variable:

function stack_check()
{
   int i;

   int *p = &i;
   printf("End of stack is %p\n", p);
}

Nicked from arduino.stackexchange.com

\$\endgroup\$
  • 2
    \$\begingroup\$ There is no guarantee that the variable "i" will be on the stack. You can not infer machine-dependent details like this from standard C. It probably works that way on machines with stacks, like the 8051, but to give this as a unqualified answer is just wrong. \$\endgroup\$ – Olin Lathrop Sep 27 '16 at 11:23
  • 2
    \$\begingroup\$ Maybe, maybe not. Surely compilers have large leeway in how to compile this. But the combination of a variable and taking the address of a variable prohibits it from using registers fo i, for example. \$\endgroup\$ – JvO Sep 27 '16 at 11:28
  • \$\begingroup\$ That's a good point about the taking the address of the variable, it must be placed in RAM. But whether it's in the stack, that's another matter. With SDCC compiler for 8051 with no memory allocation directives, it's placed in a static address. SDCC uses a call tree allocation to overlay local variables in static addresses by default and code void * GetStack() {int i; return &i;} compiles into _GetStack: mov dptr,#_GetStack_i_1_1; mov b,#0x00; ret. I think that it's compiler and memory model dependent and asm is the only way to go. \$\endgroup\$ – PkP Sep 27 '16 at 11:49
  • \$\begingroup\$ "Maybe, maybe not." Exactly. That's the point. You can't rely on it. That's why this is not a good answer, at least not without a lot more constraints and warnings. \$\endgroup\$ – Olin Lathrop Sep 27 '16 at 12:59
  • \$\begingroup\$ By taking the address of a variable, you ensure that it is not stored in a register. This behavior is only guaranteed "between the lines" by the C standard though. If you assume that all such variables always get register storage class, then the code will work. But the C standard actually does not enforce this - it only enforces that register variables cannot have their address taken. \$\endgroup\$ – Lundin Sep 27 '16 at 13:25
-1
\$\begingroup\$

[Edit] This not the correct answer, as Fritz's answer is clearly what was looked for :) But I'll let this answer remain here for the discussion of calling conventions. Especially the variadic functions (those with a variable number of arguments) are interesting in this respect.


This is in addition to JvO's answer, that suggests to get the stack pointer by getting the address of a stack allocated variable. I've also used this technique. But it was noted by Olin that the variable might not be allocated from the stack, which is also true. This lead me to think about the following approach:

void *GetStack(int *i, ...) {
    return &i;
}

The variable arguments passing guarantees, that the first parameter must be placed in a RAM address, since the rest of the arguments are guaranteed to follow it in memory (the first argument must be passable to a va_start macro), and as such there's a good chance that it is in the stack. So while it doesn't pinpoint the exact address of the top of stack, it could be quite close and should be worth a try if JvO's method doesn't work.

PS. if you know that the first argement must or must not be a pointer, please go ahead and edit the answer.


[Edit] I just realized that the question was specific to 8051, so I did a quick test on SDCC compiler. SDCC uses a call tree allocation to overlay local variables in static addresses by default and the code

void * GetStack() {
  int i; 
  return &i;
} 

compiles into

_GetStack: 
  mov dptr,#_GetStack_i_1_1
  mov b,#0x00
  ret

Meaning that i is not in the stack, it's a static address decided by the compiler. I think that it's so compiler and memory model dependent that asm is the only real way to go.


My first suggested function

void *GetStack2(int *i, ...) {
    return &i;
}

seems to do a bit better, it compiles into:

GetStack2:
        push    _bp
        mov     _bp,sp
        mov     a,_bp
        add     a,#0xfb
        mov     r2,a
        mov     r3,#0x00
        mov     r4,#0x0
        mov     dpl,r2
        mov     dph,r3
        mov     b,r4
        mov     sp,_bp
        pop     _bp
        ret

which at least references SP. With asm the code could be made much cleaner, I suppose.

\$\endgroup\$
  • 1
    \$\begingroup\$ Couldn't the function's parameters be stored in registers? \$\endgroup\$ – m.Alin Sep 27 '16 at 11:48
  • \$\begingroup\$ @m.Alin, no, because the variable arguments list needs a pointer go get the address of the first argument and registers don't have addresses... \$\endgroup\$ – PkP Sep 27 '16 at 11:54
  • 2
    \$\begingroup\$ @PkP: But according to the OP, referencing SP is forbidden. \$\endgroup\$ – Fritz Sep 27 '16 at 12:03
  • \$\begingroup\$ @Fritz, oops, missed that. Hmm.. this is getting interesting. Could he use malloca() to get some memory? That for sure allocates from the stack. \$\endgroup\$ – PkP Sep 27 '16 at 12:07
  • 1
    \$\begingroup\$ @PkP on the 8051 CPU registers do have memory addresses. But the whole premise of using the functional call as a forcer is mistaken unless one has more specific details of the compiler's behavior than provided. \$\endgroup\$ – Chris Stratton Sep 27 '16 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.