1

The book Numerical recipes, 2nd edition (http://numerical.recipes) uses the following code to allocate/deallocate a memory for a vector v with subscripts [nl..nh]:

#define NR_END 1
#define FREE_ARG char*

float *vector(long nl, long nh)
/* allocate a float vector with subscript range v[nl..nh] */
{
  float *v;

  v=(float *)malloc((size_t) ((nh-nl+1+NR_END)*sizeof(float)));
  if (!v) nrerror("allocation failure in vector()");
  return v-nl+NR_END;
}

void free_vector(float *v, long nl, long nh)
/* free a float vector allocated with vector() */
{
  free((FREE_ARG) (v+nl-NR_END));
}

Question 1: What is the purpose of adding/subtracting NR_END elements?

Question 2: What is the purpose of converting float * to char * in free_vector?

I understand that +1 in malloc is due to the inclusive right boundary of the array (which is non-inclusive usually in C).

Dmitry Kabanov
  • 710
  • 1
  • 7
  • 20
  • 1) Numerical Recipes uses first_index=1 indexing ( because it is basically converted FORTRAN code, which used offset=1 indexes) 2) before ANSI /c89 /c90 there was no `void*` and malloc and free used char pointers. – joop Nov 19 '18 at 16:32
  • @joop It doesn't use 1 indexing, the function lets you choose the first index. – interjay Nov 19 '18 at 16:32
  • For nl=0 it returns something different from what malloc returned. – joop Nov 19 '18 at 16:36
  • https://stackoverflow.com/q/41489210/2235885 for an example of someone assuming zero-based indexing. – joop Nov 19 '18 at 17:38
  • @joop, thanks for the explanation of `char *` in C before the 1989 standard. – Dmitry Kabanov Nov 19 '18 at 18:53
  • ... but the strange thing is they do use `size_t` which also appeared in c89/c90. (K&R2) The code might have been an attempt to migrate gradually to a more sane addressing model. @interjay: the *abstract* high-level matrix-code in the book assumes 1-based indexing, like most mathematiciens do in books (and in FORTRAN). The pointer-juggling is an ugly hack to accomodate that. It has caused a lot of confusion. – joop Nov 20 '18 at 12:12
  • @joop Yes, this code can be used for 1-based indexing or for indexing based on any other number (though the latter might not be done in the book). As I explained in my answer, if all you wanted was 1-based indexing then there is a much simpler solution that doesn't require the ugly pointer arithmetic hack: Simply allocate one more value than needed and don't use the 0th element. – interjay Nov 20 '18 at 12:19

1 Answers1

1

  1. Suppose you had nl=1 and NR_END=0. Then the returned pointer would be out of bounds (it points before the allocated block). This is undefined behavior and can lead to incorrect results, although it is unlikely to cause problems on major compilers because the pointer would be incremented back before it is dereferenced.

    To avoid this undefined behavior, you can set NR_END to the maximum expected value of nl (which is 1 in the book). This guarantees that the returned pointer is valid. However, the implementation given in the question is still incorrect, because v-nl+NR_END decrements by nl before incrementing by NR_END. A correct implementation would be v+NR_END-nl.

    Note that if nl only ever has non-negative values, a much simpler implementation would be to simply allocate nh+1 values, and then you don't need any pointer arithmetic after malloc or before free.

    Here you can see a quote from the book explaining this, from pages 940-941 of the second edition. Some quotes:

    it might happen in rare cases (and probably only on a segmented machine) that the expression b-1 has no representation at all. If this occurs, then there is no guarantee that the relation b=(b-1)+1 is satisfied.

    [....]

    the parameter NR_END is used as a number of extra storage locations allocated at the beginning of every vector or matrix block, simply for the purpose of making offset pointer references guaranteed-representable.

  2. The cast to char* is not needed in any standardized version of C. It may have been needed in ancient versions. Casting the return value of malloc is also not needed.

interjay
  • 107,303
  • 21
  • 270
  • 254
  • 1
    I'm not buying your explanation of `NR_END`. What you say is *true*, but if indeed values of `nl` different from 0 and 1 are not supported then it is sufficient to add `NR_END` to the size of the allocation, as indeed is done. `vector()` could then simply return the value from `malloc()` without doing any arithmetic on it, and `vector_free()` would not need to account for the same. – John Bollinger Nov 19 '18 at 17:29
  • @JohnBollinger It isn't my explanation, it is the book's explanation, See [here](https://www.edaboard.com/showthread.php?6955-C-question!-help-with-malloc-code-understanding&s=0d43995c6e045aa25bd62d0a295093ee&p=27906&viewfull=1#post27906). I did say in my answer that it would be much simpler to not perform any pointer arithmetic. It is in general quite bad code. – interjay Nov 19 '18 at 17:30
  • @interjay, thanks for the explanation! I wish I were more patient and looked at the book more carefully before asking my question here :-) I accept your answer. – Dmitry Kabanov Nov 19 '18 at 19:19
  • @interjay, regarding your third paragraph (starting with 'Note that if nl only ever has non-negative values'). Are you sure what you say is correct? I think, it is applicable only if you whant array to be indexed by 0, 1, ..., nh (inclusive). This routine expects the caller to index an array by nl, nl+1, ..., nh (inclusive). – Dmitry Kabanov Nov 19 '18 at 19:20
  • @DmitryKabanov Yes, I'm sure. I haven't read the book but it looks like they intend `nl` to have only the values 0 or 1, in which case this would work and be much simpler. If `nl` can be negative then you do need the pointer arithmetic. – interjay Nov 19 '18 at 20:35
  • You haven't explain why the macro is called `NL_END` when it defines the amount of extra memory to allocate at the start of the buffer. – Tim Randall Nov 19 '18 at 20:52
  • @TimRandall I don't know why it's called that, you'll have to ask the book authors. Thanks for the dishonest downvote though. – interjay Nov 19 '18 at 21:01
  • 1
    Thanks for the assumption of bad faith – Tim Randall Nov 19 '18 at 21:39