1f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#include "libufdt_sysdeps.h" 2f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 3f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#include <debug.h> 4f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#include <stdio.h> 5f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#include <stdlib.h> 6f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#include <sys/types.h> 7f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 8f6c209b3f409f879305ac9837524b9d34c850de6Li Chenint dto_print(const char *fmt, ...) { 9f6c209b3f409f879305ac9837524b9d34c850de6Li Chen int err; 10f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 11f6c209b3f409f879305ac9837524b9d34c850de6Li Chen va_list ap; 12f6c209b3f409f879305ac9837524b9d34c850de6Li Chen va_start(ap, fmt); 13f6c209b3f409f879305ac9837524b9d34c850de6Li Chen err = _dvprintf(fmt, ap); 14f6c209b3f409f879305ac9837524b9d34c850de6Li Chen va_end(ap); 15f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 16f6c209b3f409f879305ac9837524b9d34c850de6Li Chen return err; 17f6c209b3f409f879305ac9837524b9d34c850de6Li Chen} 18f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 19f6c209b3f409f879305ac9837524b9d34c850de6Li Chen/* Codes from 20f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * https://android.googlesource.com/platform/bionic.git/+/eclair-release/libc/stdlib/qsort.c 21f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * Start 22f6c209b3f409f879305ac9837524b9d34c850de6Li Chen */ 23f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 24f6c209b3f409f879305ac9837524b9d34c850de6Li Chen/* $OpenBSD: qsort.c,v 1.10 2005/08/08 08:05:37 espie Exp $ */ 25f6c209b3f409f879305ac9837524b9d34c850de6Li Chen/*- 26f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * Copyright (c) 1992, 1993 27f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * The Regents of the University of California. All rights reserved. 28f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * 29f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * Redistribution and use in source and binary forms, with or without 30f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * modification, are permitted provided that the following conditions 31f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * are met: 32f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * 1. Redistributions of source code must retain the above copyright 33f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * notice, this list of conditions and the following disclaimer. 34f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * 2. Redistributions in binary form must reproduce the above copyright 35f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * notice, this list of conditions and the following disclaimer in the 36f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * documentation and/or other materials provided with the distribution. 37f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * 3. Neither the name of the University nor the names of its contributors 38f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * may be used to endorse or promote products derived from this software 39f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * without specific prior written permission. 40f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * 41f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 42f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 45f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * SUCH DAMAGE. 52f6c209b3f409f879305ac9837524b9d34c850de6Li Chen */ 53f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 54f6c209b3f409f879305ac9837524b9d34c850de6Li Chenstatic __inline char *med3(char *, char *, char *, 55f6c209b3f409f879305ac9837524b9d34c850de6Li Chen int (*)(const void *, const void *)); 56f6c209b3f409f879305ac9837524b9d34c850de6Li Chenstatic __inline void swapfunc(char *, char *, int, int); 57f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#define min(a, b) (a) < (b) ? a : b 58f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 59f6c209b3f409f879305ac9837524b9d34c850de6Li Chen/* 60f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". 61f6c209b3f409f879305ac9837524b9d34c850de6Li Chen */ 62f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#define swapcode(TYPE, parmi, parmj, n) \ 63f6c209b3f409f879305ac9837524b9d34c850de6Li Chen { \ 64f6c209b3f409f879305ac9837524b9d34c850de6Li Chen long i = (n) / sizeof(TYPE); \ 65f6c209b3f409f879305ac9837524b9d34c850de6Li Chen TYPE *pi = (TYPE *)(parmi); \ 66f6c209b3f409f879305ac9837524b9d34c850de6Li Chen TYPE *pj = (TYPE *)(parmj); \ 67f6c209b3f409f879305ac9837524b9d34c850de6Li Chen do { \ 68f6c209b3f409f879305ac9837524b9d34c850de6Li Chen TYPE t = *pi; \ 69f6c209b3f409f879305ac9837524b9d34c850de6Li Chen *pi++ = *pj; \ 70f6c209b3f409f879305ac9837524b9d34c850de6Li Chen *pj++ = t; \ 71f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } while (--i > 0); \ 72f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 73f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#define SWAPINIT(a, es) \ 74f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swaptype = ((char *)a - (char *)0) % sizeof(long) || es % sizeof(long) \ 75f6c209b3f409f879305ac9837524b9d34c850de6Li Chen ? 2 \ 76f6c209b3f409f879305ac9837524b9d34c850de6Li Chen : es == sizeof(long) ? 0 : 1; 77f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 78f6c209b3f409f879305ac9837524b9d34c850de6Li Chenstatic __inline void swapfunc(char *a, char *b, int n, int swaptype) { 79f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (swaptype <= 1) swapcode(long, a, b, n) else swapcode(char, a, b, n) 80f6c209b3f409f879305ac9837524b9d34c850de6Li Chen} 81f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 82f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#define swap(a, b) \ 83f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (swaptype == 0) { \ 84f6c209b3f409f879305ac9837524b9d34c850de6Li Chen long t = *(long *)(a); \ 85f6c209b3f409f879305ac9837524b9d34c850de6Li Chen *(long *)(a) = *(long *)(b); \ 86f6c209b3f409f879305ac9837524b9d34c850de6Li Chen *(long *)(b) = t; \ 87f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } else \ 88f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swapfunc(a, b, es, swaptype) 89f6c209b3f409f879305ac9837524b9d34c850de6Li Chen#define vecswap(a, b, n) \ 90f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if ((n) > 0) swapfunc(a, b, n, swaptype) 91f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 92f6c209b3f409f879305ac9837524b9d34c850de6Li Chenstatic __inline char *med3(char *a, char *b, char *c, 93f6c209b3f409f879305ac9837524b9d34c850de6Li Chen int (*cmp)(const void *, const void *)) { 94f6c209b3f409f879305ac9837524b9d34c850de6Li Chen return cmp(a, b) < 0 ? (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a)) 95f6c209b3f409f879305ac9837524b9d34c850de6Li Chen : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c)); 96f6c209b3f409f879305ac9837524b9d34c850de6Li Chen} 97f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 98f6c209b3f409f879305ac9837524b9d34c850de6Li Chenvoid qsort(void *aa, size_t n, size_t es, 99f6c209b3f409f879305ac9837524b9d34c850de6Li Chen int (*cmp)(const void *, const void *)) { 100f6c209b3f409f879305ac9837524b9d34c850de6Li Chen char *pa, *pb, *pc, *pd, *pl, *pm, *pn; 101f6c209b3f409f879305ac9837524b9d34c850de6Li Chen int d, r, swaptype, swap_cnt; 102f6c209b3f409f879305ac9837524b9d34c850de6Li Chen char *a = aa; 103f6c209b3f409f879305ac9837524b9d34c850de6Li Chenloop: 104f6c209b3f409f879305ac9837524b9d34c850de6Li Chen SWAPINIT(a, es); 105f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap_cnt = 0; 106f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (n < 7) { 107f6c209b3f409f879305ac9837524b9d34c850de6Li Chen for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 108f6c209b3f409f879305ac9837524b9d34c850de6Li Chen for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es) 109f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap(pl, pl - es); 110f6c209b3f409f879305ac9837524b9d34c850de6Li Chen return; 111f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 112f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pm = (char *)a + (n / 2) * es; 113f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (n > 7) { 114f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pl = (char *)a; 115f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pn = (char *)a + (n - 1) * es; 116f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (n > 40) { 117f6c209b3f409f879305ac9837524b9d34c850de6Li Chen d = (n / 8) * es; 118f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pl = med3(pl, pl + d, pl + 2 * d, cmp); 119f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pm = med3(pm - d, pm, pm + d, cmp); 120f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pn = med3(pn - 2 * d, pn - d, pn, cmp); 121f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 122f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pm = med3(pl, pm, pn, cmp); 123f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 124f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap(a, pm); 125f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pa = pb = (char *)a + es; 126f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 127f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pc = pd = (char *)a + (n - 1) * es; 128f6c209b3f409f879305ac9837524b9d34c850de6Li Chen for (;;) { 129f6c209b3f409f879305ac9837524b9d34c850de6Li Chen while (pb <= pc && (r = cmp(pb, a)) <= 0) { 130f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (r == 0) { 131f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap_cnt = 1; 132f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap(pa, pb); 133f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pa += es; 134f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 135f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pb += es; 136f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 137f6c209b3f409f879305ac9837524b9d34c850de6Li Chen while (pb <= pc && (r = cmp(pc, a)) >= 0) { 138f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (r == 0) { 139f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap_cnt = 1; 140f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap(pc, pd); 141f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pd -= es; 142f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 143f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pc -= es; 144f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 145f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (pb > pc) break; 146f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap(pb, pc); 147f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap_cnt = 1; 148f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pb += es; 149f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pc -= es; 150f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 151f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if (swap_cnt == 0) { /* Switch to insertion sort */ 152f6c209b3f409f879305ac9837524b9d34c850de6Li Chen for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) 153f6c209b3f409f879305ac9837524b9d34c850de6Li Chen for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es) 154f6c209b3f409f879305ac9837524b9d34c850de6Li Chen swap(pl, pl - es); 155f6c209b3f409f879305ac9837524b9d34c850de6Li Chen return; 156f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 157f6c209b3f409f879305ac9837524b9d34c850de6Li Chen pn = (char *)a + n * es; 158f6c209b3f409f879305ac9837524b9d34c850de6Li Chen r = min(pa - (char *)a, pb - pa); 159f6c209b3f409f879305ac9837524b9d34c850de6Li Chen vecswap(a, pb - r, r); 160f6c209b3f409f879305ac9837524b9d34c850de6Li Chen r = min(pd - pc, pn - pd - (int)es); 161f6c209b3f409f879305ac9837524b9d34c850de6Li Chen vecswap(pb, pn - r, r); 162f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if ((r = pb - pa) > (int)es) qsort(a, r / es, es, cmp); 163f6c209b3f409f879305ac9837524b9d34c850de6Li Chen if ((r = pd - pc) > (int)es) { 164f6c209b3f409f879305ac9837524b9d34c850de6Li Chen /* Iterate rather than recurse to save stack space */ 165f6c209b3f409f879305ac9837524b9d34c850de6Li Chen a = pn - r; 166f6c209b3f409f879305ac9837524b9d34c850de6Li Chen n = r / es; 167f6c209b3f409f879305ac9837524b9d34c850de6Li Chen goto loop; 168f6c209b3f409f879305ac9837524b9d34c850de6Li Chen } 169f6c209b3f409f879305ac9837524b9d34c850de6Li Chen /* qsort(pn - r, r / es, es, cmp); */ 170f6c209b3f409f879305ac9837524b9d34c850de6Li Chen} 171f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 172f6c209b3f409f879305ac9837524b9d34c850de6Li Chen/* End of the copied qsort. */ 173f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 174f6c209b3f409f879305ac9837524b9d34c850de6Li Chenvoid dto_qsort(void *base, size_t nmemb, size_t size, 175f6c209b3f409f879305ac9837524b9d34c850de6Li Chen int (*compar)(const void *, const void *)) { 176f6c209b3f409f879305ac9837524b9d34c850de6Li Chen qsort(base, nmemb, size, compar); 177f6c209b3f409f879305ac9837524b9d34c850de6Li Chen} 178f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 179f6c209b3f409f879305ac9837524b9d34c850de6Li Chen/* Assuming the following functions are already defined in the 180f6c209b3f409f879305ac9837524b9d34c850de6Li Chen * bootloader source with the names conforming to POSIX. 181f6c209b3f409f879305ac9837524b9d34c850de6Li Chen */ 182f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 183f6c209b3f409f879305ac9837524b9d34c850de6Li Chenvoid *dto_malloc(size_t size) { return malloc(size); } 184f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 185f6c209b3f409f879305ac9837524b9d34c850de6Li Chenvoid dto_free(void *ptr) { free(ptr); } 186f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 187f6c209b3f409f879305ac9837524b9d34c850de6Li Chenchar *dto_strchr(const char *s, int c) { return strchr(s, c); } 188f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 189f6c209b3f409f879305ac9837524b9d34c850de6Li Chenunsigned long int dto_strtoul(const char *nptr, char **endptr, int base) { 190f6c209b3f409f879305ac9837524b9d34c850de6Li Chen return strtoul(nptr, endptr, base); 191f6c209b3f409f879305ac9837524b9d34c850de6Li Chen} 192f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 193f6c209b3f409f879305ac9837524b9d34c850de6Li Chensize_t dto_strlen(const char *s) { return strlen(s); } 194f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 1953407a9c362f9c3930c68ab0548184a8215a9f8bdSzuWei Linint dto_memcmp(const void *lhs, const void *rhs, size_t n) { 1963407a9c362f9c3930c68ab0548184a8215a9f8bdSzuWei Lin return memcmp(lhs, rhs, n); 1973407a9c362f9c3930c68ab0548184a8215a9f8bdSzuWei Lin} 1983407a9c362f9c3930c68ab0548184a8215a9f8bdSzuWei Lin 199f6c209b3f409f879305ac9837524b9d34c850de6Li Chenvoid *dto_memcpy(void *dest, const void *src, size_t n) { 200f6c209b3f409f879305ac9837524b9d34c850de6Li Chen return memcpy(dest, src, n); 201f6c209b3f409f879305ac9837524b9d34c850de6Li Chen} 202f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 203f6c209b3f409f879305ac9837524b9d34c850de6Li Chenint dto_strcmp(const char *s1, const char *s2) { return strcmp(s1, s2); } 204f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 205f6c209b3f409f879305ac9837524b9d34c850de6Li Chenint dto_strncmp(const char *s1, const char *s2, size_t n) { 206f6c209b3f409f879305ac9837524b9d34c850de6Li Chen return strncmp(s1, s2, n); 207f6c209b3f409f879305ac9837524b9d34c850de6Li Chen} 208f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 209f6c209b3f409f879305ac9837524b9d34c850de6Li Chenvoid *dto_memchr(const void *s, int c, size_t n) { return memchr(s, c, n); } 210f6c209b3f409f879305ac9837524b9d34c850de6Li Chen 211f6c209b3f409f879305ac9837524b9d34c850de6Li Chenvoid *dto_memset(void *s, int c, size_t n) { return memset(s, c, n); } 212