Loading ...
Sorry, an error occurred while loading the content.

Re: [PBML] Complicated Array Management...? (Or at least I think so)

Expand Messages
  • fooguy89
    Hey Jeff, thanks for the input. I hadn t even thought of doing a binary search. That s what I get for doing another few hours of programming AFTER I get home
    Message 1 of 6 , Oct 18, 2005
    • 0 Attachment
      Hey Jeff, thanks for the input. I hadn't even thought of doing a
      binary search. That's what I get for doing another few hours of
      programming AFTER I get home from doing 8 hours of programming during
      the day.

      Thanks for your assistance.


      --- In perl-beginner@yahoogroups.com, Jeff 'japhy' Pinyan <japhy@p...>
      wrote:
      >
      > On Oct 18, fooguy89 said:
      >
      > > A few typical entries might look like this:
      > >
      > > _My_function 80105230 000002de
      > > _Yet_another_function 8010550e 00000025
      > > _More_stuff 80105533 00000010
      >
      > Since elements 2 and 3 are an offset and a length, they are all you
      need
      > to determine if a given address is located in a particular function.
      >
      > > I have another file that has a list of addresses that are pointers to
      > > within the functions. For example:
      > >
      > > 80105234 (This pointer points to within _My_function)
      > > 8010551E (This pointer points to within _Yet_another_function)
      >
      > > Given an address, how can I figure out what function it came from?
      >
      > I wouldn't suggest making an element for EVERY number possible in your
      > data set; that's a memory hog if there ever was one.
      >
      > First, I would store the data as an array of array or hash references:
      >
      > my @functions;
      >
      > while (<DEFINITIONS>) {
      > push @functions, [split];
      > }
      >
      > Now @functions holds ['name', 0xSTART, 0xLENGTH] for each function.
      Now,
      > assuming this data is sorted by starting address, we can do a binary
      > search on it to find out where a random address $addr is:
      >
      > my $addr = ...; # some random address
      >
      > # starting range is the entire set of functions
      > my ($first, $last) = (0, $#functions);
      > my $guess;
      >
      > # choose a guess in the middle of the current range
      > while ($guess = ($last - $first)/2) {
      > my $data = $functions[$guess];
      >
      > # is $addr within THIS function?
      > if ($data->[1] <= $addr and $addr < ($data->[1] + $data->[2])) {
      > last; # $guess holds the index, $functions[$guess][0] is the
      name
      > }
      >
      > # is $addr in an earlier function?
      > if ($addr < $data->[1]) {
      > $last = $guess;
      > }
      > # otherwise, $addr is in a later function
      > else {
      > $first = $guess;
      > }
      > }
      >
      > The algorithm might be a little off; I will admit I have not tested it,
      > but it looks ok to me.
      >
      > --
      > Jeff "japhy" Pinyan % How can we ever be the sold short or
      > RPI Acacia Brother #734 % the cheated, we who for every service
      > http://www.perlmonks.org/ % have long ago been overpaid?
      > http://princeton.pm.org/ % -- Meister Eckhart
      >
    Your message has been successfully submitted and would be delivered to recipients shortly.