219 /* From atexit() manpage, it's safe with glibc 2.2.3 on Linux. */ |
227 /* From atexit() manpage, it's safe with glibc 2.2.3 on Linux. */ |
220 # define HB_USE_ATEXIT 1 |
228 # define HB_USE_ATEXIT 1 |
221 # endif |
229 # endif |
222 # elif defined(_MSC_VER) || defined(__MINGW32__) |
230 # elif defined(_MSC_VER) || defined(__MINGW32__) |
223 /* For MSVC: |
231 /* For MSVC: |
224 * http://msdn.microsoft.com/en-ca/library/tze57ck3.aspx |
232 * https://msdn.microsoft.com/en-us/library/tze57ck3.aspx |
225 * http://msdn.microsoft.com/en-ca/library/zk17ww08.aspx |
233 * https://msdn.microsoft.com/en-us/library/zk17ww08.aspx |
226 * mingw32 headers say atexit is safe to use in shared libraries. |
234 * mingw32 headers say atexit is safe to use in shared libraries. |
227 */ |
235 */ |
228 # define HB_USE_ATEXIT 1 |
236 # define HB_USE_ATEXIT 1 |
229 # elif defined(__ANDROID__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6)) |
237 # elif defined(__ANDROID__) |
230 /* This was fixed in Android NKD r8 or r8b: |
238 /* This is available since Android NKD r8 or r8b: |
231 * https://code.google.com/p/android/issues/detail?id=6455 |
239 * https://issuetracker.google.com/code/p/android/issues/detail?id=6455 |
232 * which introduced GCC 4.6: |
|
233 * https://developer.android.com/tools/sdk/ndk/index.html |
|
234 */ |
240 */ |
235 # define HB_USE_ATEXIT 1 |
241 # define HB_USE_ATEXIT 1 |
236 # elif defined(__APPLE__) |
242 # elif defined(__APPLE__) |
237 /* For macOS and related platforms, the atexit man page indicates |
243 /* For macOS and related platforms, the atexit man page indicates |
238 * that it will be invoked when the library is unloaded, not only |
244 * that it will be invoked when the library is unloaded, not only |
239 * at application exit. |
245 * at application exit. |
240 */ |
246 */ |
241 # define HB_USE_ATEXIT 1 |
247 # define HB_USE_ATEXIT 1 |
242 # endif |
248 # endif |
243 #endif |
249 #endif |
|
250 #ifdef HB_NO_ATEXIT |
|
251 # undef HB_USE_ATEXIT |
|
252 #endif |
244 |
253 |
245 /* Basics */ |
254 /* Basics */ |
246 |
255 |
247 #undef MIN |
256 #undef MIN |
248 template <typename Type> |
257 template <typename Type> |
522 return ((v - 1) | 3) + 1; |
531 return ((v - 1) | 3) + 1; |
523 } |
532 } |
524 |
533 |
525 |
534 |
526 |
535 |
|
536 /* |
|
537 * |
|
538 * Utility types |
|
539 * |
|
540 */ |
|
541 |
|
542 #define HB_DISALLOW_COPY_AND_ASSIGN(TypeName) \ |
|
543 TypeName(const TypeName&); \ |
|
544 void operator=(const TypeName&) |
|
545 |
|
546 /* |
|
547 * Static pools |
|
548 */ |
|
549 |
|
550 /* Global nul-content Null pool. Enlarge as necessary. */ |
|
551 |
|
552 #define HB_NULL_POOL_SIZE 264 |
|
553 static_assert (HB_NULL_POOL_SIZE % sizeof (void *) == 0, "Align HB_NULL_POOL_SIZE."); |
|
554 |
|
555 #ifdef HB_NO_VISIBILITY |
|
556 static |
|
557 #else |
|
558 extern HB_INTERNAL |
|
559 #endif |
|
560 void * const _hb_NullPool[HB_NULL_POOL_SIZE / sizeof (void *)] |
|
561 #ifdef HB_NO_VISIBILITY |
|
562 = {} |
|
563 #endif |
|
564 ; |
|
565 /* Generic nul-content Null objects. */ |
|
566 template <typename Type> |
|
567 static inline Type const & Null (void) { |
|
568 static_assert (sizeof (Type) <= HB_NULL_POOL_SIZE, "Increase HB_NULL_POOL_SIZE."); |
|
569 return *reinterpret_cast<Type const *> (_hb_NullPool); |
|
570 } |
|
571 #define Null(Type) Null<Type>() |
|
572 |
|
573 /* Specializaiton for arbitrary-content arbitrary-sized Null objects. */ |
|
574 #define DEFINE_NULL_DATA(Namespace, Type, data) \ |
|
575 } /* Close namespace. */ \ |
|
576 static const char _Null##Type[sizeof (Namespace::Type) + 1] = data; /* +1 is for nul-termination in data */ \ |
|
577 template <> \ |
|
578 /*static*/ inline const Namespace::Type& Null<Namespace::Type> (void) { \ |
|
579 return *reinterpret_cast<const Namespace::Type *> (_Null##Type); \ |
|
580 } \ |
|
581 namespace Namespace { \ |
|
582 /* The following line really exists such that we end in a place needing semicolon */ \ |
|
583 static_assert (Namespace::Type::min_size + 1 <= sizeof (_Null##Type), "Null pool too small. Enlarge.") |
|
584 |
|
585 |
|
586 /* Global writable pool. Enlarge as necessary. */ |
|
587 |
|
588 /* To be fully correct, CrapPool must be thread_local. However, we do not rely on CrapPool |
|
589 * for correct operation. It only exist to catch and divert program logic bugs instead of |
|
590 * causing bad memory access. So, races there are not actually introducing incorrectness |
|
591 * in the code. Has ~12kb binary size overhead to have it, also clang build fails with it. */ |
|
592 #ifdef HB_NO_VISIBILITY |
|
593 static |
|
594 #else |
|
595 extern HB_INTERNAL |
|
596 #endif |
|
597 /*thread_local*/ void * _hb_CrapPool[HB_NULL_POOL_SIZE / sizeof (void *)] |
|
598 #ifdef HB_NO_VISIBILITY |
|
599 = {} |
|
600 #endif |
|
601 ; |
|
602 /* CRAP pool: Common Region for Access Protection. */ |
|
603 template <typename Type> |
|
604 static inline Type& Crap (void) { |
|
605 static_assert (sizeof (Type) <= HB_NULL_POOL_SIZE, "Increase HB_NULL_POOL_SIZE."); |
|
606 Type *obj = reinterpret_cast<Type *> (_hb_CrapPool); |
|
607 *obj = Null(Type); |
|
608 return *obj; |
|
609 } |
|
610 #define Crap(Type) Crap<Type>() |
|
611 |
|
612 template <typename Type> |
|
613 struct CrapOrNull { |
|
614 static inline Type & get (void) { return Crap(Type); } |
|
615 }; |
|
616 template <typename Type> |
|
617 struct CrapOrNull<const Type> { |
|
618 static inline Type const & get (void) { return Null(Type); } |
|
619 }; |
|
620 #define CrapOrNull(Type) CrapOrNull<Type>::get () |
|
621 |
|
622 |
|
623 |
527 /* arrays and maps */ |
624 /* arrays and maps */ |
528 |
625 |
529 |
626 |
530 #define HB_PREALLOCED_ARRAY_INIT {0, 0, nullptr} |
627 #define HB_PREALLOCED_ARRAY_INIT {0, 0, nullptr} |
531 template <typename Type, unsigned int StaticSize=16> |
628 template <typename Type, unsigned int StaticSize=8> |
532 struct hb_prealloced_array_t |
629 struct hb_vector_t |
533 { |
630 { |
534 unsigned int len; |
631 unsigned int len; |
535 unsigned int allocated; |
632 unsigned int allocated; |
536 Type *array; |
633 bool successful; |
|
634 Type *arrayZ; |
537 Type static_array[StaticSize]; |
635 Type static_array[StaticSize]; |
538 |
636 |
539 void init (void) |
637 void init (void) |
540 { |
638 { |
541 len = 0; |
639 len = 0; |
542 allocated = ARRAY_LENGTH (static_array); |
640 allocated = ARRAY_LENGTH (static_array); |
543 array = static_array; |
641 successful = true; |
544 } |
642 arrayZ = static_array; |
545 |
643 } |
546 inline Type& operator [] (unsigned int i) { return array[i]; } |
644 |
547 inline const Type& operator [] (unsigned int i) const { return array[i]; } |
645 inline Type& operator [] (unsigned int i) |
|
646 { |
|
647 if (unlikely (i >= len)) |
|
648 return Crap (Type); |
|
649 return arrayZ[i]; |
|
650 } |
|
651 inline const Type& operator [] (unsigned int i) const |
|
652 { |
|
653 if (unlikely (i >= len)) |
|
654 return Null(Type); |
|
655 return arrayZ[i]; |
|
656 } |
548 |
657 |
549 inline Type *push (void) |
658 inline Type *push (void) |
550 { |
659 { |
551 if (unlikely (!resize (len + 1))) |
660 if (unlikely (!resize (len + 1))) |
552 return nullptr; |
661 return &Crap(Type); |
553 |
662 return &arrayZ[len - 1]; |
554 return &array[len - 1]; |
663 } |
|
664 inline Type *push (const Type& v) |
|
665 { |
|
666 Type *p = push (); |
|
667 *p = v; |
|
668 return p; |
555 } |
669 } |
556 |
670 |
557 /* Allocate for size but don't adjust len. */ |
671 /* Allocate for size but don't adjust len. */ |
558 inline bool alloc(unsigned int size) |
672 inline bool alloc (unsigned int size) |
559 { |
673 { |
|
674 if (unlikely (!successful)) |
|
675 return false; |
|
676 |
560 if (likely (size <= allocated)) |
677 if (likely (size <= allocated)) |
561 return true; |
678 return true; |
562 |
679 |
563 /* Reallocate */ |
680 /* Reallocate */ |
564 |
681 |
566 while (size >= new_allocated) |
683 while (size >= new_allocated) |
567 new_allocated += (new_allocated >> 1) + 8; |
684 new_allocated += (new_allocated >> 1) + 8; |
568 |
685 |
569 Type *new_array = nullptr; |
686 Type *new_array = nullptr; |
570 |
687 |
571 if (array == static_array) { |
688 if (arrayZ == static_array) |
|
689 { |
572 new_array = (Type *) calloc (new_allocated, sizeof (Type)); |
690 new_array = (Type *) calloc (new_allocated, sizeof (Type)); |
573 if (new_array) |
691 if (new_array) |
574 memcpy (new_array, array, len * sizeof (Type)); |
692 memcpy (new_array, arrayZ, len * sizeof (Type)); |
575 } else { |
693 } |
|
694 else |
|
695 { |
576 bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type)); |
696 bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type)); |
577 if (likely (!overflows)) { |
697 if (likely (!overflows)) |
578 new_array = (Type *) realloc (array, new_allocated * sizeof (Type)); |
698 new_array = (Type *) realloc (arrayZ, new_allocated * sizeof (Type)); |
579 } |
|
580 } |
699 } |
581 |
700 |
582 if (unlikely (!new_array)) |
701 if (unlikely (!new_array)) |
|
702 { |
|
703 successful = false; |
583 return false; |
704 return false; |
584 |
705 } |
585 array = new_array; |
706 |
|
707 arrayZ = new_array; |
586 allocated = new_allocated; |
708 allocated = new_allocated; |
587 |
709 |
588 return true; |
710 return true; |
589 } |
711 } |
590 |
712 |
591 inline bool resize (unsigned int size) |
713 inline bool resize (int size_) |
592 { |
714 { |
|
715 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; |
593 if (!alloc (size)) |
716 if (!alloc (size)) |
594 return false; |
717 return false; |
595 |
718 |
|
719 if (size > len) |
|
720 memset (arrayZ + len, 0, (size - len) * sizeof (*arrayZ)); |
|
721 |
596 len = size; |
722 len = size; |
597 return true; |
723 return true; |
598 } |
724 } |
599 |
725 |
600 inline void pop (void) |
726 inline void pop (void) |
601 { |
727 { |
|
728 if (!len) return; |
602 len--; |
729 len--; |
603 } |
730 } |
604 |
731 |
605 inline void remove (unsigned int i) |
732 inline void remove (unsigned int i) |
606 { |
733 { |
607 if (unlikely (i >= len)) |
734 if (unlikely (i >= len)) |
608 return; |
735 return; |
609 memmove (static_cast<void *> (&array[i]), |
736 memmove (static_cast<void *> (&arrayZ[i]), |
610 static_cast<void *> (&array[i + 1]), |
737 static_cast<void *> (&arrayZ[i + 1]), |
611 (len - i - 1) * sizeof (Type)); |
738 (len - i - 1) * sizeof (Type)); |
612 len--; |
739 len--; |
613 } |
740 } |
614 |
741 |
615 inline void shrink (unsigned int l) |
742 inline void shrink (int size_) |
616 { |
743 { |
617 if (l < len) |
744 unsigned int size = size_ < 0 ? 0u : (unsigned int) size_; |
618 len = l; |
745 if (size < len) |
|
746 len = size; |
619 } |
747 } |
620 |
748 |
621 template <typename T> |
749 template <typename T> |
622 inline Type *find (T v) { |
750 inline Type *find (T v) { |
623 for (unsigned int i = 0; i < len; i++) |
751 for (unsigned int i = 0; i < len; i++) |
624 if (array[i] == v) |
752 if (arrayZ[i] == v) |
625 return &array[i]; |
753 return &arrayZ[i]; |
626 return nullptr; |
754 return nullptr; |
627 } |
755 } |
628 template <typename T> |
756 template <typename T> |
629 inline const Type *find (T v) const { |
757 inline const Type *find (T v) const { |
630 for (unsigned int i = 0; i < len; i++) |
758 for (unsigned int i = 0; i < len; i++) |
631 if (array[i] == v) |
759 if (arrayZ[i] == v) |
632 return &array[i]; |
760 return &arrayZ[i]; |
633 return nullptr; |
761 return nullptr; |
634 } |
762 } |
635 |
763 |
636 inline void qsort (int (*cmp)(const void*, const void*)) |
764 inline void qsort (int (*cmp)(const void*, const void*)) |
637 { |
765 { |
638 ::qsort (array, len, sizeof (Type), cmp); |
766 ::qsort (arrayZ, len, sizeof (Type), cmp); |
639 } |
767 } |
640 |
768 |
641 inline void qsort (void) |
769 inline void qsort (void) |
642 { |
770 { |
643 ::qsort (array, len, sizeof (Type), Type::cmp); |
771 ::qsort (arrayZ, len, sizeof (Type), Type::cmp); |
644 } |
772 } |
645 |
773 |
646 inline void qsort (unsigned int start, unsigned int end) |
774 inline void qsort (unsigned int start, unsigned int end) |
647 { |
775 { |
648 ::qsort (array + start, end - start, sizeof (Type), Type::cmp); |
776 ::qsort (arrayZ + start, end - start, sizeof (Type), Type::cmp); |
649 } |
777 } |
650 |
778 |
651 template <typename T> |
779 template <typename T> |
652 inline Type *lsearch (const T &x) |
780 inline Type *lsearch (const T &x) |
653 { |
781 { |
654 for (unsigned int i = 0; i < len; i++) |
782 for (unsigned int i = 0; i < len; i++) |
655 if (0 == this->array[i].cmp (&x)) |
783 if (0 == this->arrayZ[i].cmp (&x)) |
656 return &array[i]; |
784 return &arrayZ[i]; |
657 return nullptr; |
785 return nullptr; |
658 } |
786 } |
659 |
787 |
660 template <typename T> |
788 template <typename T> |
661 inline Type *bsearch (const T &x) |
789 inline Type *bsearch (const T &x) |
662 { |
790 { |
663 unsigned int i; |
791 unsigned int i; |
664 return bfind (x, &i) ? &array[i] : nullptr; |
792 return bfind (x, &i) ? &arrayZ[i] : nullptr; |
665 } |
793 } |
666 template <typename T> |
794 template <typename T> |
667 inline const Type *bsearch (const T &x) const |
795 inline const Type *bsearch (const T &x) const |
668 { |
796 { |
669 unsigned int i; |
797 unsigned int i; |
670 return bfind (x, &i) ? &array[i] : nullptr; |
798 return bfind (x, &i) ? &arrayZ[i] : nullptr; |
671 } |
799 } |
672 template <typename T> |
800 template <typename T> |
673 inline bool bfind (const T &x, unsigned int *i) const |
801 inline bool bfind (const T &x, unsigned int *i) const |
674 { |
802 { |
675 int min = 0, max = (int) this->len - 1; |
803 int min = 0, max = (int) this->len - 1; |
676 while (min <= max) |
804 while (min <= max) |
677 { |
805 { |
678 int mid = (min + max) / 2; |
806 int mid = (min + max) / 2; |
679 int c = this->array[mid].cmp (&x); |
807 int c = this->arrayZ[mid].cmp (&x); |
680 if (c < 0) |
808 if (c < 0) |
681 max = mid - 1; |
809 max = mid - 1; |
682 else if (c > 0) |
810 else if (c > 0) |
683 min = mid + 1; |
811 min = mid + 1; |
684 else |
812 else |
685 { |
813 { |
686 *i = mid; |
814 *i = mid; |
687 return true; |
815 return true; |
688 } |
816 } |
689 } |
817 } |
690 if (max < 0 || (max < (int) this->len && this->array[max].cmp (&x) > 0)) |
818 if (max < 0 || (max < (int) this->len && this->arrayZ[max].cmp (&x) > 0)) |
691 max++; |
819 max++; |
692 *i = max; |
820 *i = max; |
693 return false; |
821 return false; |
694 } |
822 } |
695 |
823 |
696 inline void finish (void) |
824 inline void fini (void) |
697 { |
825 { |
698 if (array != static_array) |
826 if (arrayZ != static_array) |
699 free (array); |
827 free (arrayZ); |
700 array = nullptr; |
828 arrayZ = nullptr; |
701 allocated = len = 0; |
829 allocated = len = 0; |
702 } |
830 } |
703 }; |
831 }; |
704 |
832 |
705 template <typename Type> |
833 template <typename Type> |
706 struct hb_auto_array_t : hb_prealloced_array_t <Type> |
834 struct hb_auto_t : Type |
707 { |
835 { |
708 hb_auto_array_t (void) { hb_prealloced_array_t<Type>::init (); } |
836 hb_auto_t (void) { Type::init (); } |
709 ~hb_auto_array_t (void) { hb_prealloced_array_t<Type>::finish (); } |
837 ~hb_auto_t (void) { Type::fini (); } |
|
838 private: /* Hide */ |
|
839 void init (void) {} |
|
840 void fini (void) {} |
710 }; |
841 }; |
|
842 template <typename Type> |
|
843 struct hb_auto_array_t : hb_auto_t <hb_vector_t <Type> > {}; |
711 |
844 |
712 |
845 |
713 #define HB_LOCKABLE_SET_INIT {HB_PREALLOCED_ARRAY_INIT} |
846 #define HB_LOCKABLE_SET_INIT {HB_PREALLOCED_ARRAY_INIT} |
714 template <typename item_t, typename lock_t> |
847 template <typename item_t, typename lock_t> |
715 struct hb_lockable_set_t |
848 struct hb_lockable_set_t |
716 { |
849 { |
717 hb_prealloced_array_t <item_t, 1> items; |
850 hb_vector_t <item_t, 1> items; |
718 |
851 |
719 inline void init (void) { items.init (); } |
852 inline void init (void) { items.init (); } |
720 |
853 |
721 template <typename T> |
854 template <typename T> |
722 inline item_t *replace_or_insert (T v, lock_t &l, bool replace) |
855 inline item_t *replace_or_insert (T v, lock_t &l, bool replace) |
973 static const bool passthru_left = true; |
1102 static const bool passthru_left = true; |
974 static const bool passthru_right = true; |
1103 static const bool passthru_right = true; |
975 template <typename T> static void process (T &o, const T &a, const T &b) { o = a ^ b; } |
1104 template <typename T> static void process (T &o, const T &a, const T &b) { o = a ^ b; } |
976 }; |
1105 }; |
977 |
1106 |
|
1107 |
|
1108 /* Compiler-assisted vectorization. */ |
|
1109 |
|
1110 /* The `vector_size' attribute was introduced in gcc 3.1. */ |
|
1111 #if defined( __GNUC__ ) && ( __GNUC__ >= 4 ) |
|
1112 #define HB_VECTOR_SIZE 128 |
|
1113 #elif !defined(HB_VECTOR_SIZE) |
|
1114 #define HB_VECTOR_SIZE 0 |
|
1115 #endif |
|
1116 |
978 /* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))). */ |
1117 /* Type behaving similar to vectorized vars defined using __attribute__((vector_size(...))). */ |
979 template <typename elt_t, unsigned int byte_size> |
1118 template <typename elt_t, unsigned int byte_size> |
980 struct hb_vector_size_t |
1119 struct hb_vector_size_t |
981 { |
1120 { |
982 elt_t& operator [] (unsigned int i) { return v[i]; } |
1121 elt_t& operator [] (unsigned int i) { return u.v[i]; } |
983 const elt_t& operator [] (unsigned int i) const { return v[i]; } |
1122 const elt_t& operator [] (unsigned int i) const { return u.v[i]; } |
984 |
1123 |
985 template <class Op> |
1124 template <class Op> |
986 inline hb_vector_size_t process (const hb_vector_size_t &o) const |
1125 inline hb_vector_size_t process (const hb_vector_size_t &o) const |
987 { |
1126 { |
988 hb_vector_size_t r; |
1127 hb_vector_size_t r; |
989 for (unsigned int i = 0; i < ARRAY_LENGTH (v); i++) |
1128 #if HB_VECTOR_SIZE |
990 Op::process (r.v[i], v[i], o.v[i]); |
1129 if (HB_VECTOR_SIZE && 0 == (byte_size * 8) % HB_VECTOR_SIZE) |
|
1130 for (unsigned int i = 0; i < ARRAY_LENGTH (u.vec); i++) |
|
1131 Op::process (r.u.vec[i], u.vec[i], o.u.vec[i]); |
|
1132 else |
|
1133 #endif |
|
1134 for (unsigned int i = 0; i < ARRAY_LENGTH (u.v); i++) |
|
1135 Op::process (r.u.v[i], u.v[i], o.u.v[i]); |
991 return r; |
1136 return r; |
992 } |
1137 } |
993 inline hb_vector_size_t operator | (const hb_vector_size_t &o) const |
1138 inline hb_vector_size_t operator | (const hb_vector_size_t &o) const |
994 { return process<HbOpOr> (o); } |
1139 { return process<HbOpOr> (o); } |
995 inline hb_vector_size_t operator & (const hb_vector_size_t &o) const |
1140 inline hb_vector_size_t operator & (const hb_vector_size_t &o) const |