Re: [PATCH v2] src/: ceil_prime(): Add function to get the lowest prime not smaller than n

[Alejandro Colomar]

On Wed, Mar 13, 2024 at 05:45:10AM -0500, G. Branden Robinson wrote:
> Hi Alex,

Hi Branden,

> At 2024-03-13T11:21:55+0100, Alejandro Colomar wrote:
> > And use it where the same logic was being open-coded.
> > 
> > While at it, fix the logic, which was incorrect in the open-coded call
> > sites, since for an input of 1, it produced 3, but the first prime is 2.
> 
> Are you sure?  That sounds like the bug I already fixed (but have not
> yet pushed).

I didn't write an exploit, as that would be a little bit more work
(including learning what is indxbib at all).

But by reading the code, I'd say yes.

$ git show master:src/utils/indxbib/indxbib.cpp \
| grepc main \
| grep -C5 is_prime;
        int requested_hash_table_size;
        check_integer_arg('h', optarg, 1, &requested_hash_table_size);
        hash_table_size = requested_hash_table_size;
        if ((hash_table_size > 2) && (hash_table_size % 2) == 0)
                hash_table_size++;
        while (!is_prime(hash_table_size))
          hash_table_size += 2;
        if (hash_table_size != requested_hash_table_size)
          warning("requested hash table size %1 is not prime: using %2"
                  " instead", optarg, hash_table_size);
      }

Let's imagine 'requested_hash_table_size' is 1.  check_integer_arg()
should let it pass.  Then it's not >2, so we skip the ++.  And then it's
not a prime, so we +=2, and then have 3.

BTW, that's the reason I was first confused and suggested raising the
minimum to 3.  I hadn't really understood what the code was trying to
do, and only knew what it was actually doing (after a quick read of the
code), and since an input of 1 resulted in an output of 3, I thought
raising the bar to 3 should be ok.  It seems not.  :)

> 
> My working copy, complete with the following debugging output, is
> attached.
> 
> $ ./build/indxbib -h 1
> ./build/indxbib: fatal error: argument to -h must not be less than 2
> $ ./build/indxbib -h 2
> ./build/indxbib: debug: using hash table size of 2
> ./build/indxbib: fatal error: no files and no -f option
> $ ./build/indxbib -h 3
> ./build/indxbib: debug: using hash table size of 3
> ./build/indxbib: fatal error: no files and no -f option
> $ ./build/indxbib -h 4
> ./build/indxbib: warning: requested hash table size 4 is not prime: using 5 
> instead
> ./build/indxbib: debug: using hash table size of 5
> ./build/indxbib: fatal error: no files and no -f option
> 
> > Also, since this is a library function, let's behave well for an input
> > of 0, and return also the first prime, 2.
> 
> I'm skeptical of adding a library function for this purpose (finding the
> smallest prime number equal to or greater than the input integer) when
> it _has_ no other call sites.

You had is_prime() with the same exact number of call sites: 2.

If you want to misbehave for an input of 0 from a library call, by
adding an assertion, well that's not too bad, since you're the only
user.  In fact, is_prime() has such an assertion, even being a library
call.  If you want me to add it, just let me know.

> In fact, the only other caller of is_prime() itself is in libbib, where
> it's not operating on a user-supplied parameter (as in a user of the
> running process).
> 
> https://git.savannah.gnu.org/cgit/groff.git/tree/src/libs/libbib/index.cpp?h=1.23.0#n603
> 
> Wouldn't it be more idiomatic C++ to migrate libbib to an STL container?

*Mis*quoting someone (was it Torvalds who wrote the Linux coding style?
I guess he was):

        First off, I'd suggest printing out a copy of the _C++_
        standard, and NOT read it.  Burn it, it's a great symbolic
        gesture.

I don't like idiomatic C++.  In fact, the only thing I like from C++ is
that I can write idiomatic C in it (or mostly; some things don't
compile, like using VLA notation in function parameters that are
pointers).

> (Not that I'm saying you should do that.)

Nice.  :)

> Regards,
> Branden

Have a lovely day!
Alex

-- 
<https://www.alejandro-colomar.es/>
Looking for a remote C programming job at the moment.

signature.asc
Description: PGP signature