Index: uspace/app/fdisk/fdisk.c =================================================================== --- uspace/app/fdisk/fdisk.c (revision ef9dac04c0fc9ea516faf7b03b19b4419267f91f) +++ uspace/app/fdisk/fdisk.c (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -167,4 +167,6 @@ } + fdisk_cap_simplify(&cap); + rc = fdisk_cap_format(&cap, &scap); if (rc != EOK) { @@ -518,4 +520,6 @@ goto error; } + + fdisk_cap_simplify(&pinfo.capacity); rc = fdisk_cap_format(&pinfo.capacity, &scap); @@ -662,4 +666,6 @@ } + fdisk_cap_simplify(&cap); + rc = fdisk_cap_format(&cap, &sdcap); if (rc != EOK) { @@ -713,4 +719,6 @@ goto error; } + + fdisk_cap_simplify(&pinfo.capacity); rc = fdisk_cap_format(&pinfo.capacity, &scap); @@ -774,4 +782,6 @@ } + fdisk_cap_simplify(&mcap); + rc = fdisk_cap_format(&mcap, &smcap); if (rc != EOK) { @@ -794,4 +804,6 @@ } + fdisk_cap_simplify(&mcap); + rc = fdisk_cap_format(&mcap, &smcap); if (rc != EOK) { @@ -817,4 +829,6 @@ } + fdisk_cap_simplify(&mcap); + rc = fdisk_cap_format(&mcap, &smcap); if (rc != EOK) { @@ -832,4 +846,6 @@ goto error; } + + fdisk_cap_simplify(&mcap); rc = fdisk_cap_format(&mcap, &smcap); Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision ef9dac04c0fc9ea516faf7b03b19b4419267f91f) +++ uspace/lib/c/Makefile (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -96,4 +96,5 @@ generic/task.c \ generic/futex.c \ + generic/imath.c \ generic/inet/addr.c \ generic/inet/endpoint.c \ Index: uspace/lib/c/generic/imath.c =================================================================== --- uspace/lib/c/generic/imath.c (revision 9854a8faee04ea815f8612666a6e4dac63db2748) +++ uspace/lib/c/generic/imath.c (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -0,0 +1,123 @@ +/* + * Copyright (c) 2015 Jiri Svoboda + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ +/** + * @file Integer mathematical functions + */ + +#include +#include +#include +#include + +/** Compute integer power of 10, unsigned 64-bit result. + * + * Fast algorithm using binary digits of exp to compute 10^exp in + * time O(log exp). + * + * @param exp Exponent + * @param res Place to store result + * @return EOK on success, ERANGE if result does not fit into result type + */ +int ipow10_u64(unsigned exp, uint64_t *res) +{ + unsigned a; + uint64_t r; + + r = 1; + a = 10; + while (true) { + if ((exp & 1) != 0) { + if ((r * a) / a != r) + return ERANGE; + r = r * a; + } + + exp = exp >> 1; + if (exp == 0) + break; + + if ((a * a) / a != a) + return ERANGE; + a = a * a; + } + + *res = r; + return EOK; +} + +/** Compute integer base 10 logarithm, unsigned 64-bit argument. + * + * For integer v, compute floor(log_10 v). Fast algorithm computing + * the binary digits of the result r in time O(log r). + * + * @param v Value to compute logarithm from + * @return Logarithm value + */ +unsigned ilog10_u64(uint64_t v) +{ + unsigned b; + unsigned e; + uint64_t p10p2[6]; + uint64_t a; + unsigned r; + + /* Determine largest b such that 10^2^b <= v */ + b = 0; + e = 1; + a = 10; + p10p2[0] = a; + + while (v / a >= a) { + ++b; + a = a * a; + e = e + e; + p10p2[b] = a; + } + + /* Determine the binary digits of largest e such that 10^e <= v */ + r = 0; + while (true) { + if (v >= p10p2[b]) { + v = v / p10p2[b]; + r = r ^ (1 << b); + } + + if (b == 0) + break; + --b; + } + + return r; +} + +/** @} + */ Index: uspace/lib/c/include/imath.h =================================================================== --- uspace/lib/c/include/imath.h (revision 9854a8faee04ea815f8612666a6e4dac63db2748) +++ uspace/lib/c/include/imath.h (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2015 Jiri Svoboda + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + * @brief Integer math functions + */ + +#ifndef LIBC_IMATH_H_ +#define LIBC_IMATH_H_ + +#include + +extern int ipow10_u64(unsigned, uint64_t *); +extern unsigned ilog10_u64(uint64_t); + +#endif + +/** + * @} + */ Index: uspace/lib/fdisk/Makefile =================================================================== --- uspace/lib/fdisk/Makefile (revision ef9dac04c0fc9ea516faf7b03b19b4419267f91f) +++ uspace/lib/fdisk/Makefile (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -33,4 +33,5 @@ SOURCES = \ + src/cap.c \ src/fdisk.c Index: uspace/lib/fdisk/include/fdisk.h =================================================================== --- uspace/lib/fdisk/include/fdisk.h (revision ef9dac04c0fc9ea516faf7b03b19b4419267f91f) +++ uspace/lib/fdisk/include/fdisk.h (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -73,4 +73,8 @@ extern int fdisk_cap_format(fdisk_cap_t *, char **); extern int fdisk_cap_parse(const char *, fdisk_cap_t *); +extern void fdisk_cap_simplify(fdisk_cap_t *); +extern void fdisk_cap_from_blocks(uint64_t, size_t, fdisk_cap_t *); +extern int fdisk_cap_to_blocks(fdisk_cap_t *, size_t, uint64_t *); + extern int fdisk_ltype_format(label_type_t, char **); extern int fdisk_fstype_format(vol_fstype_t, char **); Index: uspace/lib/fdisk/include/types/fdisk.h =================================================================== --- uspace/lib/fdisk/include/types/fdisk.h (revision ef9dac04c0fc9ea516faf7b03b19b4419267f91f) +++ uspace/lib/fdisk/include/types/fdisk.h (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -77,7 +77,22 @@ #define CU_LIMIT (cu_ybyte + 1) -/** Partition capacity */ -typedef struct { - uint64_t value; +/** Partition capacity. + * + * Partition capacity represents both value and precision. + * It is a decimal floating point value combined with a decimal + * capacity unit. There is an integer mantisa @c m which in combination + * with the number of decimal positions @c dp gives a decimal floating-point + * number. E.g. for m = 1025 and dp = 2 the number is 10.25. If the unit + * cunit = cu_kbyte, the capacity is 10.25 kByte, i.e. 10 250 bytes. + * + * Note that 1.000 kByte is equivalent to 1000 Byte, but 1 kByte is less + * precise. + */ +typedef struct { + /** Mantisa */ + uint64_t m; + /** Decimal positions */ + unsigned dp; + /** Capacity unit */ fdisk_cunit_t cunit; } fdisk_cap_t; Index: uspace/lib/fdisk/src/cap.c =================================================================== --- uspace/lib/fdisk/src/cap.c (revision 9854a8faee04ea815f8612666a6e4dac63db2748) +++ uspace/lib/fdisk/src/cap.c (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -0,0 +1,224 @@ +/* + * Copyright (c) 2015 Jiri Svoboda + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libfdisk + * @{ + */ +/** + * @file Disk management library. + */ + +#include +#include +#include +#include +#include + +/** Simplified capacity parameters */ +enum { + /** Simplified capacity maximum integer digits */ + scap_max_idig = 3, + /** Simplified capacity maximum significant digits */ + scap_max_sdig = 4 +}; + +static const char *cu_str[] = { + [cu_byte] = "B", + [cu_kbyte] = "kB", + [cu_mbyte] = "MB", + [cu_gbyte] = "GB", + [cu_tbyte] = "TB", + [cu_pbyte] = "PB", + [cu_ebyte] = "EB", + [cu_zbyte] = "ZB", + [cu_ybyte] = "YB" +}; + +void fdisk_cap_from_blocks(uint64_t nblocks, size_t block_size, + fdisk_cap_t *cap) +{ + uint64_t tsize; + + tsize = nblocks * block_size; + cap->m = tsize; + cap->dp = 0; + cap->cunit = cu_byte; +} + +/** Convert capacity to blocks. + * + * If the value of bytes is not integer, it is properly rounded. If the number + * of bytes is not divisible by the number of blocks, it is rounded + * up to an integer number of blocks. + */ +int fdisk_cap_to_blocks(fdisk_cap_t *cap, size_t block_size, + uint64_t *blocks) +{ + int exp; + uint64_t bytes; + uint64_t f; + int rc; + + // XXX Check for overflow + + exp = cap->cunit * 3 - cap->dp; + if (exp < 0) { + rc = ipow10_u64(-exp, &f); + if (rc != EOK) + return ERANGE; + bytes = (cap->m + (f / 2)) / f; + } else { + rc = ipow10_u64(exp, &f); + if (rc != EOK) + return ERANGE; + bytes = cap->m * f; + } + + *blocks = (bytes + block_size - 1) / block_size; + return EOK; +} + +/** Simplify and round capacity to a human-friendly form. + * + * Change unit and round the number so that we have at most three integer + * digits and at most two fractional digits, e.g abc.xy . + */ +void fdisk_cap_simplify(fdisk_cap_t *cap) +{ + uint64_t div; + uint64_t maxv; + unsigned sdig; + unsigned rdig; + int rc; + + printf("before: m=%" PRIu64 " dp=%u cunit=%d\n", + cap->m, cap->dp, cap->cunit); + + /* Change units so that we have at most @c scap_max_idig integer digits */ + rc = ipow10_u64(scap_max_idig, &maxv); + assert(rc == EOK); + + rc = ipow10_u64(cap->dp, &div); + assert(rc == EOK); + + while (cap->m / div >= maxv) { + ++cap->cunit; + cap->dp += 3; + div = div * 1000; + } + + /* Round the number so that we have at most @c scap_max_sdig significant digits */ + sdig = 1 + ilog10_u64(cap->m); /* number of significant digits */ + if (sdig > scap_max_sdig) { + /* Number of digits to remove */ + rdig = sdig - scap_max_sdig; + if (rdig > cap->dp) + rdig = cap->dp; + + rc = ipow10_u64(rdig, &div); + assert(rc == EOK); + + cap->m = (cap->m + (div / 2)) / div; + cap->dp -= rdig; + } + + printf("after: m=%" PRIu64 " dp=%u cunit=%d\n", + cap->m, cap->dp, cap->cunit); +} + +int fdisk_cap_format(fdisk_cap_t *cap, char **rstr) +{ + int rc; + const char *sunit; + uint64_t ipart; + uint64_t fpart; + uint64_t div; + + sunit = NULL; + + if (cap->cunit < 0 || cap->cunit >= CU_LIMIT) + assert(false); + + rc = ipow10_u64(cap->dp, &div); + if (rc != EOK) + return rc; + + ipart = cap->m / div; + fpart = cap->m % div; + + sunit = cu_str[cap->cunit]; + if (cap->dp > 0) { + rc = asprintf(rstr, "%" PRIu64 ".%0*" PRIu64 " %s", ipart, + (int)cap->dp, fpart, sunit); + } else { + rc = asprintf(rstr, "%" PRIu64 " %s", ipart, sunit); + } + if (rc < 0) + return ENOMEM; + + return EOK; +} + +int fdisk_cap_parse(const char *str, fdisk_cap_t *cap) +{ + char *eptr; + char *p; + unsigned long val; + int i; + + val = strtoul(str, &eptr, 10); + + while (*eptr == ' ') + ++eptr; + + if (*eptr == '\0') { + cap->cunit = cu_byte; + } else { + for (i = 0; i < CU_LIMIT; i++) { + if (str_lcasecmp(eptr, cu_str[i], + str_length(cu_str[i])) == 0) { + p = eptr + str_size(cu_str[i]); + while (*p == ' ') + ++p; + if (*p == '\0') + goto found; + } + } + + return EINVAL; +found: + cap->cunit = i; + } + + cap->m = val; + cap->dp = 0; + return EOK; +} + +/** @} + */ Index: uspace/lib/fdisk/src/fdisk.c =================================================================== --- uspace/lib/fdisk/src/fdisk.c (revision ef9dac04c0fc9ea516faf7b03b19b4419267f91f) +++ uspace/lib/fdisk/src/fdisk.c (revision 9854a8faee04ea815f8612666a6e4dac63db2748) @@ -46,16 +46,4 @@ #include -static const char *cu_str[] = { - [cu_byte] = "B", - [cu_kbyte] = "kB", - [cu_mbyte] = "MB", - [cu_gbyte] = "GB", - [cu_tbyte] = "TB", - [cu_pbyte] = "PB", - [cu_ebyte] = "EB", - [cu_zbyte] = "ZB", - [cu_ybyte] = "YB" -}; - static int fdisk_dev_add_parts(fdisk_dev_t *); static void fdisk_dev_remove_parts(fdisk_dev_t *); @@ -257,7 +245,5 @@ return EIO; - cap->value = bsize * nblocks; - cap->cunit = cu_byte; - + fdisk_cap_from_blocks(nblocks, bsize, cap); return EOK; } @@ -330,6 +316,6 @@ dev->ext_part = part; - part->capacity.cunit = cu_byte; - part->capacity.value = part->nblocks * dev->dinfo.block_size; + fdisk_cap_from_blocks(part->nblocks, dev->dinfo.block_size, + &part->capacity); part->part_id = partid; @@ -619,7 +605,5 @@ block_fini(dev->sid); - cap->value = bsize * nblocks; - cap->cunit = cu_byte; - + fdisk_cap_from_blocks(nblocks, bsize, cap); return EOK; } @@ -783,6 +767,5 @@ } - cap->value = nb * dev->dinfo.block_size; - cap->cunit = cu_byte; + fdisk_cap_from_blocks(nb, dev->dinfo.block_size, cap); return EOK; } @@ -812,6 +795,5 @@ } while (fdisk_free_range_next(&fr)); - cap->value = totb * dev->dinfo.block_size; - cap->cunit = cu_byte; + fdisk_cap_from_blocks(totb, dev->dinfo.block_size, cap); return EOK; } @@ -882,57 +864,4 @@ { memset(pspec, 0, sizeof(fdisk_part_spec_t)); -} - -int fdisk_cap_format(fdisk_cap_t *cap, char **rstr) -{ - int rc; - const char *sunit; - - sunit = NULL; - - if (cap->cunit < 0 || cap->cunit >= CU_LIMIT) - assert(false); - - sunit = cu_str[cap->cunit]; - rc = asprintf(rstr, "%" PRIu64 " %s", cap->value, sunit); - if (rc < 0) - return ENOMEM; - - return EOK; -} - -int fdisk_cap_parse(const char *str, fdisk_cap_t *cap) -{ - char *eptr; - char *p; - unsigned long val; - int i; - - val = strtoul(str, &eptr, 10); - - while (*eptr == ' ') - ++eptr; - - if (*eptr == '\0') { - cap->cunit = cu_byte; - } else { - for (i = 0; i < CU_LIMIT; i++) { - if (str_lcasecmp(eptr, cu_str[i], - str_length(cu_str[i])) == 0) { - p = eptr + str_size(cu_str[i]); - while (*p == ' ') - ++p; - if (*p == '\0') - goto found; - } - } - - return EINVAL; -found: - cap->cunit = i; - } - - cap->value = val; - return EOK; } @@ -1108,12 +1037,9 @@ vbd_part_spec_t *vpspec) { - uint64_t cbytes; aoff64_t req_blocks; aoff64_t fblock0; aoff64_t fnblocks; aoff64_t hdrb; - uint64_t block_size; label_pcnt_t pcnt; - unsigned i; int index; int rc; @@ -1121,15 +1047,6 @@ printf("fdisk_part_spec_prepare() - dev=%p pspec=%p vpspec=%p\n", dev, pspec, vpspec); - printf("fdisk_part_spec_prepare() - block size\n"); - block_size = dev->dinfo.block_size; - printf("fdisk_part_spec_prepare() - cbytes\n"); - cbytes = pspec->capacity.value; - printf("fdisk_part_spec_prepare() - cunit\n"); - for (i = 0; i < pspec->capacity.cunit; i++) - cbytes = cbytes * 1000; - - printf("fdisk_part_spec_prepare() - req_blocks block_size=%zu\n", - block_size); - req_blocks = (cbytes + block_size - 1) / block_size; + fdisk_cap_to_blocks(&pspec->capacity, dev->dinfo.block_size, &req_blocks); + req_blocks = fdisk_ba_align_up(dev, req_blocks);